Counting & Radix Sort

Why the lower bound exists

Any comparison-based sort can be modelled as a decision tree: each internal node compares two elements; each leaf is a final ordering. There are n! orderings, so the tree has at least n! leaves. A binary tree with n! leaves has depth at least log₂(n!) = Θ(n log n). So in the worst case, comparison sorts perform Θ(n log n) comparisons.

The argument assumes comparison is the only allowed operation. If you can index into the data using its value (as counting sort does) the lower bound no longer applies. We're not asking "is A < B?"; we're asking "where in this fixed structure does A go?"

Counting sort

Given an array of integers in [0, k], count occurrences of each value, then emit them in order.

def counting_sort(a, k):
    counts = [0] * (k + 1)
    for x in a:
        counts[x] += 1
    out, idx = [0] * len(a), 0
    for v, c in enumerate(counts):
        for _ in range(c):
            out[idx] = v; idx += 1
    return out

Time: O(n + k). Space: O(n + k), the counts array and the output array. The technique is fast when k is comparable to n (or smaller). For k much larger than n (e.g., 32-bit integers), the counts array dominates memory and the technique stops being viable.

Stable counting sort

The version above doesn't preserve relative order of equal-valued objects (it doesn't matter for plain integers). For stable sort over (key, value) pairs, build a prefix-sum of counts and place objects from right to left:

def stable_counting(a, k, key=lambda x: x):
    counts = [0] * (k + 1)
    for x in a:
        counts[key(x)] += 1
    # Prefix sums: counts[v] becomes "first slot for keys <= v".
    for v in range(1, k + 1):
        counts[v] += counts[v - 1]
    out = [None] * len(a)
    # Right-to-left placement preserves order of equal keys.
    for x in reversed(a):
        counts[key(x)] -= 1
        out[counts[key(x)]] = x
    return out

The right-to-left traversal is the key to stability. Forward traversal would reverse the order of equal-valued objects.

Radix sort

For integers (or strings) too wide for counting sort, sort digit by digit. The least-significant-digit (LSD) variant runs counting sort on each digit position, from rightmost to leftmost. Each round is O(n + base); w rounds give O(w(n + base)) total. For 32-bit integers in base 256, w = 4 and base = 256, so the algorithm is O(n) with a small constant.

def radix_sort(a, base=10):
    if not a: return a
    max_val = max(a)
    exp = 1                                          # 1, base, base², …
    out = list(a)
    while max_val // exp > 0:
        out = stable_counting(out, base - 1, key=lambda x, e=exp: (x // e) % base)
        exp *= base
    return out

Each round uses the stable counting sort from before, keyed on the current digit. Stability is essential: the order produced by sorting on the lower digits must be preserved when we sort on higher digits. Without stability, the final output is wrong.

LSD radix sort is the version you'd actually implement. MSD (most-significant-digit) variants exist and are useful for string sorting and external sorts, but they're more complex.

Bucket sort

A close cousin. Suppose the input is uniformly distributed over a known range. Distribute elements into n buckets (one per index), each of which holds a small number on average. Sort each bucket with a simple algorithm (insertion sort works well for small buckets). Concatenate.

Time: O(n) expected if the input is uniform; O(n²) worst case if everything lands in one bucket. Memory: O(n) for the buckets. Used in problems like Maximum Gap (the maximum difference between successive sorted elements) where bucket sort's structure beats comparison-based sorting.

When each applies

Cache and constant-factor reality

Asymptotic complexity isn't the whole story. Comparison sorts touch memory in regular, cache-friendly patterns; radix sort's writes can scatter across the bucket array, hurting cache hit rate.

For small inputs (n < 10⁴ or so) or non-trivial keys, Timsort or introsort almost always beats radix in wall-clock time despite the asymptotic advantage. The break-even point depends on hardware; benchmark your specific use case before switching to a non-comparison sort.

String sorting

Both counting and radix generalise to strings. For fixed-length strings, treat each character as a "digit"; w-round radix sort sorts the whole array in O(n · w) time. For variable-length strings, MSD radix sort is the standard approach. Suffix arrays (used in genome assembly and full-text indexes) rely on these techniques.

When non-comparison sorts fail

• Unbounded key range. Counting sort's k can be much larger than n. The counts array becomes the bottleneck.
• Non-integer keys with no obvious encoding. Sorting custom objects by some attribute is fine with comparison sorts; radix requires you to encode the key as an integer or string.
• Small inputs. For n < 50, comparison sorts win on constant factors.
• External sorting. When data doesn't fit in memory, the I/O pattern matters more than the comparison model. Merge sort variants dominate here.

Where beginners go wrong

• Using counting sort with huge k. Memory blows up; the algorithm degrades to slower-than-comparison sort. Check the input range before applying.
• Unstable counting sort inside radix sort. Radix relies on stability at every digit. Forward placement after prefix sums reverses equal-key order, wrong output.
• Using LSD radix when MSD is more natural. For variable-length strings, MSD is the right shape. LSD requires padding all strings to equal length, which is wasteful.
• Counting sort with negative integers. Counts array indexes from 0; negative keys need an offset. The fix is one line; forgetting it is an array-index crash.

What to read next

The Dutch National Flag piece is a specialised counting-sort variant for tiny alphabets. The Sorting & Search module covers the comparison-sort family for context. The Frequency Counting piece is the close relative used for top-K and grouping problems.