Counting Sort

#How does it work?

Counting sort never compares elements with each other. Instead it counts how many of each value there are.

Running totals of the counts tell where each value starts in the output; if 5 values are smaller than 3, the first 3 goes to slot 5. Then the elements are walked left to right and dropped straight into place.

When the value range (k) is small it runs in linear time, beating the O(n log n) lower bound of comparison sorts. It keeps equal values in order, so it is stable.

#Live animation

for each value v in a: count[v] = count[v] + 1
start[v] = how many values are smaller than v   // prefix sums
for each value v in a (left to right):
  output[start[v]] = v; start[v] = start[v] + 1
a = output

#Step by step

1. 01Count how many of each value there are.
2. 02Turn the counts into running totals: each value's starting slot in the output.
3. 03Walk the array left to right; put each element at the next slot for its value.
4. 04Advance that value's slot counter.
5. 05Copy the output back.

#Example code

The same algorithm in 8 languages. Every program is compiled, run and checked to print the same output.

def counting_sort(a: list[int]) -> list[int]:
    """Sorts non-negative integers without comparing elements. Stable."""
    if not a:
        return a
    count = [0] * (max(a) + 1)
    for v in a:
        count[v] += 1
    # Running totals: count[v] becomes the slot just after the last v.
    for v in range(1, len(count)):
        count[v] += count[v - 1]
    output = [0] * len(a)
    # Walk from the right so equal values keep their order.
    for v in reversed(a):
        count[v] -= 1
        output[count[v]] = v
    return output


print(*counting_sort([4, 2, 2, 8, 3, 3, 1]))

#Complexity

n is the number of elements and k the value range (max − min + 1). If k is small compared to n, it runs in linear time. If values span a huge range (say 1 to a billion), the count array becomes enormous and the algorithm impractical.

#When to use it?

Very fast for integers in a small range (ages, grades, pixel values 0–255). It is the helper inside each digit pass of radix sort. Not suitable for decimals or wide ranges.

#Practice

Log in to answer questions and save your progress.

#Up next

Lessons that build on this one:

• Radix Sort