Counting sort explained: how it works, code and complexity

What problem counting sort solves

Any sort that only compares pairs of elements needs Ω(n log n) comparisons in the worst case. Counting sort avoids this limit by not comparing at all: it uses the key itself as an array index. When the keys are small integers, such as exam scores from 0 to 100, ages, bytes from 0 to 255 or star ratings, this is faster than any comparison sort.

The price is memory proportional to the range of keys. Sorting a handful of 64-bit integers that are spread across the whole range would need an impossibly large count array.

The idea and a worked example

Sort [4, 2, 2, 8, 3, 3, 1], whose values lie in the range 0 to 8 (k = 9).

1. Count each value: count[v] is the number of times v appears.
2. Prefix sums: replace each count with the number of elements less than or equal to that value. Then count[v] is one past the last position where v belongs.
3. Place elements: walk the input from right to left; for each value v, decrease count[v] and write v at that position. Walking right to left keeps equal values in their original order.

So the 1 goes to index 0, the two 2s to indexes 1 and 2, the two 3s to 3 and 4, the 4 to index 5 and the 8 to index 6. Result: [1, 2, 2, 3, 3, 4, 8].

Python implementation

This stable version sorts any objects by an integer key between 0 and k - 1.

def counting_sort(items, k, key=lambda x: x):
    """Stable sort of items by integer key in range(k)."""
    count = [0] * k
    for x in items:
        count[key(x)] += 1
    for v in range(1, k):                # prefix sums
        count[v] += count[v - 1]
    out = [None] * len(items)
    for x in reversed(items):            # right to left: stable
        count[key(x)] -= 1
        out[count[key(x)]] = x
    return out

print(counting_sort([4, 2, 2, 8, 3, 3, 1], k=9))
# [1, 2, 2, 3, 3, 4, 8]
people = [("Ana", 3), ("Bo", 1), ("Cy", 3), ("Di", 2)]
print(counting_sort(people, k=4, key=lambda p: p[1]))
# [('Bo', 1), ('Di', 2), ('Ana', 3), ('Cy', 3)]

When you only sort plain integers and do not need stability, a simpler version rebuilds the output from the counts. This variant also handles negative numbers by shifting by the minimum:

def counting_sort_ints(nums):
    if not nums:
        return []
    lo, hi = min(nums), max(nums)
    count = [0] * (hi - lo + 1)
    for x in nums:
        count[x - lo] += 1
    out = []
    for offset, c in enumerate(count):
        out.extend([offset + lo] * c)
    return out

print(counting_sort_ints([3, -1, 2, -1, 0]))   # [-1, -1, 0, 2, 3]

Time and space complexity

Counting sort is linear when k is O(n). If k is much larger than n, for example 1,000 values in the range 0 to 10⁹, the count array dominates and a comparison sort or radix sort is better.

How counting sort compares with other sorts

Here k is the size of the key range, d the number of digits and b the base used by radix sort. Counting sort is stable when elements are placed using prefix sums from right to left. The simple rebuild-from-counts version produces the same result for plain integers but cannot carry other data along with the key.

Variants and common mistakes

• Radix sort runs a stable counting sort once per digit, which extends the idea to large integers and fixed-length strings.
• Bucket sort spreads values over buckets by range and sorts each bucket; it is fast when values are uniformly distributed.
• Counting without sorting: often you only need the counts, for example to build a histogram or to find the mode. collections.Counter does that directly.

When to use counting sort

Use it when keys are integers in a small range compared with the number of elements: grades, ages, days of the month, bytes, color channel values from 0 to 255, or small enum values. It is also the inner step of radix sort and of suffix-array construction algorithms. In interviews, it appears in questions such as sort colors (values 0, 1, 2), sorting by frequency, and the H-index, and in the classic question of how to beat the O(n log n) bound for comparison sorts.