Counting sort visualization

Counting sort is a sorting algorithm for whole numbers in a small, known range 0 to k. It never compares two values. It counts how often each value occurs, turns the counts into positions, and writes every value straight to its place. In this lesson k is 9.

How it works

1. Make a count array C with a cell for each value 0 to k, all zero.
2. Count: for each value in the array, add one to its cell.
3. Prefix sums: replace each cell with the sum of itself and the cell before it. Now C[v] is the number of values that are at most v.
4. Place: read the array from right to left. Subtract one from C[v], and write v into slot C[v] of an output array B.
5. Copy B back into the array.

Time and space complexity

The loops run over the n values and the k + 1 cells, whatever the order of the values.

• Time, best, average and worst: O(n + k). The comparison count is always 0. The work is writes: k + 1 to fill C, then n, k and 3n.
• Space: O(n + k), for the count array (k + 1 cells) and the output array (n cells). It is not in place.

The O(n log n) limit applies only to sorts that compare values. Counting sort uses values as positions instead.

A worked example

Sort 4, 1, 3, 4, 3, 0, 1 with k = 9. The counting loop leaves C[0] to C[9] as 1, 2, 0, 2, 2, 0, 0, 0, 0, 0: one 0, two 1s, two 3s and two 4s. The prefix sums turn that into 1, 3, 3, 5, 7, 7, 7, 7, 7, 7, so C[3] = 5 says that 5 values are at most 3. Now read the array from right to left. Each value goes to slot C[v] - 1 of B, and C[v] drops by one.

Copying B back gives 0, 1, 1, 3, 3, 4, 4. Look at the equal values: the 4 at index 3 took slot 6 and the 4 at index 0 took slot 5, so the one that came first stays first. That is stability at work. The run makes 0 comparisons and 47 writes, which is the formula above: 10 to fill C, 7 for the counting loop, 9 for the prefix sums, 14 for the decrements and placements, and 7 for the copy.

Pseudocode

A holds n whole numbers from 0 to k, C has k + 1 cells and B has n cells. The code counts indexes from 0.

COUNTING-SORT(A, k)
    let C[0..k] be a new array of zeros
    let B[0..n-1] be a new array
    for j = 0 to n - 1
        C[A[j]] = C[A[j]] + 1
    for i = 1 to k
        C[i] = C[i] + C[i - 1]
    for j = n - 1 downto 0
        C[A[j]] = C[A[j]] - 1
        B[C[A[j]]] = A[j]
    for i = 0 to n - 1
        A[i] = B[i]

The four loops run n, k, n and n times, so the time is O(n + k). Changing n - 1 downto 0 to 0 to n - 1 is the mistake in the box below: the values still end up sorted, but equal values come out reversed.

Stability

Counting sort is stable. Because the placement loop reads from the right, the last copy of a value takes the last free slot for it, and equal values keep their original order. This is what makes radix sort work.

When to use it, and when not to

• Use it when the values are integers in a range k that is small compared with n: ages, scores, digits.
• Avoid it when the range is huge. Sorting values up to a billion would need a count array of a billion cells, even for ten values.

Where it is used

• The digit sort inside radix sort. Radix sort calls a stable counting sort once for each digit, with ten possible digit values. Radix sort needs the stability of counting sort, which is why CLRS describes the two together.
• Small-range data. Ages, exam scores, grades and the bytes of a text are whole numbers in a small range. With 256 possible byte values, counting sort orders any number of bytes with a count array of 256 cells. Counting how many pixels have each brightness value, a histogram of an image, is the first two steps of the same algorithm.
• Sorting records by a small key. Stability lets you sort first by one field and then by another. Sort a class list by name, then by grade with counting sort: students with the same grade stay in name order.

Variations and related ideas

For negative numbers, subtract the smallest value first so that the range starts at 0. When the range is large but the numbers have few digits, radix sort applies counting sort one digit at a time, with a small k each time; the counting sort vs radix sort page runs both on the same inputs. Bucket sort (CLRS, section 8.4) handles real numbers spread evenly over a range. To see where counting sort does badly, compare it with comparison sorts such as merge sort, quick sort and heap sort: it wins when k is small and loses when k is much larger than n.