6.7 Counting Sort

Counting sort replaces comparisons with counting. It assumes keys come from a small integer range and uses that structure to achieve linear time. Instead of ordering elements directly, it counts how many times each key appears and reconstructs the sorted output from those counts.

Problem

You have an array A[0..n-1] where each element is an integer in a known range [0, k]. You want a stable sorting algorithm with linear time complexity.

Solution

Count occurrences of each value, compute prefix sums to determine final positions, and write elements into an output array.

counting_sort(A, k):
  n = length(A)

  count = array of size k + 1 filled with 0
  output = array of size n

  for i = 0 to n - 1:
    count[A[i]] = count[A[i]] + 1

  for v = 1 to k:
    count[v] = count[v] + count[v - 1]

  for i = n - 1 down to 0:
    v = A[i]
    count[v] = count[v] - 1
    output[count[v]] = A[i]

  return output

The backward scan in the final loop preserves stability.

Example

Input:

[3, 1, 2, 1, 0]

Count occurrences:

count = [1, 2, 1, 1]

Compute prefix sums:

count = [1, 3, 4, 5]

This means:

value 0 ends before index 1
value 1 ends before index 3
value 2 ends before index 4
value 3 ends before index 5

Now place elements from right to left:

output = [0, 1, 1, 2, 3]

Counting Invariant

After the prefix sum step, count[v] represents the number of elements in A that are less than or equal to v. This defines the final index boundary for each value.

During the placement loop, after processing elements A[i+1..n-1], the following holds:

• The suffix of output contains exactly those processed elements in sorted order
• count[v] points to the next free position for value v

When placing A[i] = v, decrementing count[v] gives the correct index where this occurrence of v should go.

Correctness

Counting sort satisfies the permutation condition because each input element is written exactly once into the output array.

It satisfies the order condition because:

• All elements with value v occupy positions between count[v-1] and count[v] - 1
• These ranges are disjoint and ordered by v

Thus, smaller values always appear before larger values.

Stability

Counting sort is stable when the placement loop scans from right to left.

Consider:

[(2, A), (1, B), (2, C)]

Processing from right to left ensures (2, C) is placed after (2, A):

[(1, B), (2, A), (2, C)]

If the loop scanned left to right, equal elements would be reversed, breaking stability.

Complexity

The running time is:

O(n + k)

where:

• n is the number of elements
• k is the size of the key range

The space usage is:

O(n + k)

This is efficient when k is small relative to n. If k is large, the memory cost dominates and the algorithm becomes impractical.

When to Use

Counting sort is appropriate when:

keys are integers in a small range
stability is required
linear time is desired

It is commonly used as a subroutine in radix sort and bucket-based algorithms.

Limitations

Counting sort cannot be applied directly to arbitrary data types. It requires a mapping from elements to integer keys in a bounded range.

If the range is large, such as 32-bit integers, the count array becomes too large to allocate.

Implementation Notes

If keys do not start at 0, shift them:

min_value = minimum(A)
use index (A[i] - min_value)

This reduces the required range.

For large sparse ranges, use coordinate compression before applying counting sort.

Common Bugs

A frequent bug is forgetting to compute prefix sums. Without them, placement positions are incorrect.

Another bug is scanning the input from left to right during placement, which breaks stability.

A third bug is allocating the count array with size k instead of k + 1, which causes out-of-bounds errors.

Takeaway

Counting sort achieves linear time by replacing comparisons with counting. It is stable, simple, and efficient when the key range is small, but unsuitable when the range is large or unbounded.