Introduction

Count Sort is a non-comparison based sorting algorithm.

Instead of comparing elements, it:

  • counts frequency of elements
  • reconstructs sorted array using counts

This algorithm works efficiently when:

  • range of values is small

This problem helps in understanding:

  • frequency arrays
  • counting techniques
  • non-comparison sorting
  • efficient sorting for limited ranges

Example

Input:arr = [4, 2, 2, 8, 3, 3, 1]

Output:
[1, 2, 2, 3, 3, 4, 8]

Explanation:
Frequencies are counted and array is rebuilt in sorted order.

Constraints

1 <= arr.length <= 10^50 <= arr[i] <= 10^5
Approach : Frequency Counting

Explanation

Count Sort works in three steps:

  1. Find maximum element
  2. Count frequency of every value
  3. Rebuild sorted array

Unlike comparison-based sorting:

  • no swapping is required

Steps

  1. Find maximum element.
  2. Create count array.
  3. Count frequencies.
  4. Rebuild sorted array.
  5. Return sorted array.

Dry Run

Input:[4, 2, 2, 8, 3, 3, 1]
Maximum element:
8

Frequency count:
1 → 1
2 → 2
3 → 2
4 → 1
8 → 1

Rebuild array:
[1, 2, 2, 3, 3, 4, 8]

Final Result:
[1, 2, 2, 3, 3, 4, 8]

Count Sort Code

Complexity Analysis

Time Complexity: O(n + k)Explanation:n elements are counted and k range values are traversed.

Space Complexity: O(k)
Explanation:
Extra count array is used.

Edge Cases

  1. Empty array
  2. Single element array
  3. Duplicate elements
  4. Already sorted array
  5. Large value ranges

Why This Problem is Important

Count Sort helps in understanding:

  1. Frequency counting
  2. Non-comparison sorting
  3. Counting arrays
  4. Efficient range-based sorting
  5. Linear-time sorting concepts

It is one of the most important non-comparison sorting algorithms.

Real-World Applications

Count Sort concepts are used in:

  1. Frequency analysis
  2. Exam score sorting
  3. Age-based grouping
  4. Histogram processing
  5. Radix Sort

Common Mistakes

  1. Incorrect count array size
  2. Forgetting maximum element
  3. Wrong rebuilding logic
  4. Handling large ranges inefficiently

Interview Tips

Interviewers often expect:

  1. O(n + k) explanation
  2. Frequency counting understanding
  3. Difference from comparison sorting

Always explain:

  • why comparisons are avoided
  • how frequencies help sorting
  • when Count Sort is efficient

Related Questions

  1. Radix Sort
  2. Bucket Sort
  3. Heap Sort
  4. Sort Colors
  5. Frequency Count

Final Takeaway

Count Sort is a fundamental non-comparison sorting algorithm that teaches frequency counting and range-based sorting techniques. Understanding Count Sort builds a strong foundation for advanced linear-time sorting algorithms and interview problems.