Counting SortCounting sort

01Why it exists

Reach for it when you see:Integer keys, a small range (k not much bigger than n), scores, ages, bytes, histograms, equal values that must keep their original order, each pass of a radix sort, and anything that has to beat O(n log n).

02The core idea

When the things being sorted are integers from a small range, there is no need to compare any two of them. Allocate a count array of length k, make one pass incrementing count[x], and you know how often every value occurs; then, going from smallest to largest, emit value v exactly count[v] times and the output is sorted. If the range does not start at 0, or includes negatives, find the minimum lo first and index with x − lo. This beats the Ω(n log n) lower bound for sorting because that bound only constrains algorithms that learn about the data by comparing; counting sort uses the value itself as an array index and learns where an element belongs in a single access, so it sits outside that model entirely (the Sorting Lower Bound lesson proves the bound).

For plain numbers the above is enough, but in practice what you sort is usually objects: students by score, orders by status, with more data riding along under each key. The stable version adds one step, a prefix accumulation: after count[v] += count[v−1], count[v] is the number of elements with key ≤ v, so the elements with key v occupy positions count[v−1] through count[v] − 1 in the output. Then scan the input from the back, and for each element with key v do count[v] −= 1 before writing it to out[count[v]]. Among the elements sharing a key, the one that came last in the input lands in the last slot of that block, the one before it in the second-to-last slot, and so on, so their relative order is exactly the input order. That is what stable means. Scanning front to back while keeping the same decrement-then-write logic reverses each block of equal keys instead.

Complexity: one pass over n elements to count, one over k slots to accumulate, and one over n elements to place, for O(n + k) time — independent of how the data happens to be arranged, so the best, average and worst cases are identical. Space is O(k) for count plus O(n) for the output array, so O(n + k) for the stable version; sorting bare integers can overwrite the original array and needs only O(k). Everything hinges on k. Over a range of 0–100, k is negligible; over 0–10⁹, the count array alone is 4 GB and k dominates O(n + k), which is the point at which you switch to radix sort and sort by a few digits at a time. The rule of thumb is that counting sort pays off when k = O(n).

Three traps come up again and again. Forgetting the shift, so a negative value indexes out of bounds. Scanning front to back while still decrementing before writing, which leaves the output sorted but not stable — and that quietly breaks radix sort. And guessing the range, so that one oversized value in the test data blows up memory; take the min and max first. Compared with the neighbouring techniques: the Hash Set / Map Patterns lesson counts occurrences with a hash table, which suits keys that are numerous and scattered, while counting sort uses an array and requires the keys to be small integers in the first place. It is not in place, and it only works on discrete integer keys, so floats and strings have to be mapped to integer keys first, or handed to the radix and bucket sorts in the next lesson.

03The algorithm

1. 1Confirm the keys are integers and find the minimum lo and maximum hi. The approach only pays off when the range k = hi − lo + 1 is within a small factor of n.
2. 2Allocate a count array of length k and make one pass over the input doing count[x − lo] += 1.
3. 3Sorting plain numbers: for v from 0 to k − 1, emit v + lo exactly count[v] times, and you are done.
4. 4Sorting objects stably: accumulate the prefix sums with count[v] += count[v − 1], so that count[v] becomes the number of elements with key ≤ v.
5. 5Scan the input from the back: do count[key] −= 1 and place the element at out[count[key]]. When the scan finishes, out holds the stably sorted result.

04Interactive demo

The shared array [5, 2, 9, 1, 7, 3, 8, 4] plus one extra 2 and one extra 5, with ᵃ and ᵇ marking the original order of the equal values. The three phases run in sequence: counting, prefix accumulation, and filling from the back. Blue marks the input element being processed and, in the output row, the slot it was just placed in; yellow marks its count slot, and green marks output that is already settled. No two elements are ever compared with each other anywhere in the run. At the end, check that 2ᵃ still precedes 2ᵇ and 5ᵃ still precedes 5ᵇ.

05Code

Two versions: a compact one for plain integers (shifting by the minimum, so negatives work), and a stable one for objects, demonstrated by sorting students by score with ties keeping their original order. The C++ stable version is a template, with the key function and the range k supplied by the caller, so each pass of a radix sort can use it directly.

# Counting sort: integer keys over the range [lo, hi], with no comparisons at all. O(n + k), k = hi - lo + 1
def counting_sort(a):
    if not a:
        return []
    lo, hi = min(a), max(a)
    count = [0] * (hi - lo + 1)
    for x in a:
        count[x - lo] += 1                   # shift by lo so negative values can index too
    out = []
    for v, c in enumerate(count):
        out.extend([v + lo] * c)             # the value v + lo occurs c times, so emit it c times
    return out


# Stable version: sorts objects whose key(x) lands in 0..k-1
def counting_sort_by_key(items, key, k):
    count = [0] * k
    for it in items:
        count[key(it)] += 1
    for v in range(1, k):
        count[v] += count[v - 1]             # now count[v] = how many elements have key <= v
    out = [None] * len(items)
    for it in reversed(items):               # fill from the back so equal keys keep their order
        count[key(it)] -= 1
        out[count[key(it)]] = it
    return out


if __name__ == "__main__":
    print(counting_sort([5, 2, 9, 1, 7, 3, 8, 4, 2, 5]))   # [1, 2, 2, 3, 4, 5, 5, 7, 8, 9]
    print(counting_sort([3, -1, 0, -1, 2]))                # [-1, -1, 0, 2, 3]
    # already in registration order; after sorting by score, equal scores stay in that order
    students = [("Amy", 88), ("Ben", 72), ("Cara", 88), ("Dan", 95), ("Eve", 72)]
    print(counting_sort_by_key(students, key=lambda s: s[1], k=101))
    # [('Ben', 72), ('Eve', 72), ('Amy', 88), ('Cara', 88), ('Dan', 95)]

06Practice

• LeetCode 1051Height Checker (heights only run 1–100, so count and compare directly)Easy
• LeetCode 1122Relative Sort Array (counting over the range 0–1000)Easy
• LeetCode 791Custom Sort String (count each of the 26 letters, then emit in the given order)Medium
• LeetCode 274H-Index (clamp citation counts above n to n, squeezing the range into 0–n)Medium
• LeetCode 2785Sort Vowels in a String (counting sort over the vowels only)Medium