Counting Sort — Ages, Grades, and Histograms

Counting sort does not compare elements against each other to decide order. Instead it counts frequencies in a bounded range, then rebuilds the output by walking those counts. That makes it perfect when values are small integers with a tight domain—think exam scores from 0–100 or pixel buckets in a tiny histogram.

Why this shows up in the real world

A city elections office might tally thousands of ballots where each vote is an integer candidate code from a fixed small list. A streaming sensor that only emits severity levels {0,1,2,3} can be sorted in linear time by counting how many of each level arrived in a window. E‑commerce dashboards sometimes bucket ages into coarse bins (18–24, 25–34) for privacy; counting sort ideas appear when you sort those discrete bins. The catch is memory: you need auxiliary space proportional to the value range, not just n, so huge sparse keys (like 64‑bit IDs) are a bad fit unless compressed.

Core idea (explained for students)

Phase 1: allocate count[r] for each value r in [min,max], scan the input and increment counts. Phase 2: walk r from low to high and write r into the output count[r] times. Because you never compare arbitrary pairs, the work is O(n + k) with k the range width. Stability is achievable if you walk counts carefully (prefix sums + backward fill). Students should contrast this with comparison lower bound Ω(n log n)—counting sort breaks that bound because it is not a comparison sort; it exploits numeric structure.

Try this in Python

def counting_sort(values: list[int]) -> list[int]:
    if not values:
        return []
    lo, hi = min(values), max(values)
    k = hi - lo + 1
    count = [0] * k
    for v in values:
        count[v - lo] += 1
    out: list[int] = []
    for i, c in enumerate(count):
        out.extend([lo + i] * c)
    return out


print(counting_sort([3, 0, 2, 3, 2]))

Common mistakes

• Using counting sort when k is gigantic—memory explodes.
• Off-by-one on inclusive ranges [min,max].
• Forgetting stable reconstruction order when duplicates must preserve input ties.

Key takeaways

• Linear time when k is small: O(n + k) time, O(k) extra space typical.
• Ideal for bounded small integers; not for arbitrary strings without mapping.
• Pair with radix sort mentally: counting sort is often a subroutine digit by digit.