Counting Sort, Radix Sort & the Comparison-Sort Lower Bound

The question this subtopic answers

Every algorithm in the previous two subtopics sorts by comparing pairs of elements — and that's not an implementation detail, it's a hard theoretical ceiling. This subtopic covers the family of sorts that sidestep comparison entirely by exploiting structure in the keys themselves (bounded integers, fixed-width numbers, small alphabets) — and, just as importantly, the proof of exactly why comparison sorts can never beat O(n log n), so you know precisely when it's even theoretically possible to do better.

The comparison-sort lower bound: why O(n log n) is a wall, not a guess

Any sorting algorithm that only learns information about the input by comparing two elements at a time (<, <=, >) can be modeled as a decision tree: each internal node is a comparison, each leaf is one possible output ordering. For n distinct elements, there are n! possible orderings, so the tree needs at least n! leaves. A binary tree with n! leaves has depth at least log₂(n!), and by Stirling's approximation, log₂(n!) = Θ(n log n). Since the depth of the tree is the worst-case number of comparisons, no comparison-based sort can do better than Ω(n log n) comparisons in the worst case — merge sort and heapsort aren't just good, they're asymptotically optimal within the comparison model.

This is worth being able to state precisely, because it's the exact justification for why the algorithms in this subtopic aren't a contradiction: they don't beat the lower bound, they escape the model it applies to by using more information than pairwise comparison (the actual bit-pattern or numeric value of each key).

Counting sort: O(n + k) when keys are small, known-range integers

If every key is an integer in a known range [0, k), you don't need to compare keys at all — you can count how many times each value occurs, then reconstruct the sorted output directly from those counts:

This is O(n + k) time and O(k) extra space — genuinely linear, beating the comparison-sort wall, but only because it isn't comparing keys at all; it's using each key's value directly as an array index. The moment k is much larger than n (e.g., sorting 100 numbers drawn from a range of a billion), this stops being a win — you'd allocate a huge, mostly-empty counts array for no benefit, which is exactly the signal to reach for radix sort instead.

Stable counting sort (needed as a building block for radix sort below, and any time you need to preserve relative order of equal keys): build a prefix-sum array over counts first, then place each element by decrementing its target position, walking the input from right to left:

Radix sort: sorting bigger numbers by their digits

Radix sort handles integers too large for a practical counting-sort range by sorting one digit (or byte) at a time, from least-significant to most-significant, using a stable counting sort as the subroutine at each digit position:

Why LSD (least-significant-digit first) and stability are non-negotiable together: each pass must preserve the relative order established by all previous, less-significant passes — an unstable counting sort as the subroutine silently produces a wrong final order. This is the single most common correctness bug when implementing radix sort from scratch.

Complexity: O(d · (n + b)) where d is the number of digits and b is the base (radix) — for fixed-width integers (e.g., 32-bit), d is a small constant, so this is effectively O(n). This is the concrete answer to "how would you sort a million numbers faster than quicksort?" — for fixed-width integer keys, radix sort's O(d·n) beats quicksort's O(n log n) once d < log n, which is true for essentially any realistic integer range once n is large. The catch, and the reason radix sort isn't the universal default: it needs keys with a decomposable fixed structure (digits, bytes, fixed-width bit fields) — it doesn't generalize to arbitrary comparable objects the way quicksort does.

Bucket sort: when keys are uniformly distributed reals

Bucket sort scatters elements into n buckets based on value (e.g., bucket_index = int(x * n) for x uniformly distributed in [0, 1)), sorts each bucket with an ordinary comparison sort (insertion sort is the standard choice, since buckets are expected to be small), then concatenates:

Expected O(n) when the input distribution is close to uniform — each bucket then holds O(1) elements on average, so the total sorting-within-buckets cost is O(n), not O(n log n). This is a probabilistic guarantee, not a worst-case one: an adversarial or heavily skewed distribution (everything landing in one bucket) degrades this to the cost of sorting that one bucket, up to O(n²) if you're unlucky and it's insertion sort on a fully-populated single bucket. State the distributional assumption out loud if you propose this — it's the whole basis for the O(n) claim.

Choosing between them

Technique	Time	When it applies	Escapes the Ω(n log n) wall by...
Comparison sort (merge/quick/heap)	O(n log n)	Always — the general-purpose default	N/A — this is the wall
Counting sort	O(n + k)	Small, known integer range [0, k)	Using the key as an index, not comparing keys
Radix sort	O(d · (n + b)) ≈ O(n) for fixed-width keys	Fixed-width integers/strings, decomposable into digits	Same as counting sort, applied digit-by-digit
Bucket sort	O(n) expected	Roughly uniformly distributed real-valued keys	Exploiting known distribution, not comparing keys

Pitfalls and interview gotchas

• Reaching for radix/counting sort on arbitrary comparable objects. These only work when you can extract a bounded, decomposable numeric key — they don't generalize to "sort these custom objects by an arbitrary comparator" the way quicksort/merge sort do.
• Using an unstable sort as radix sort's per-digit subroutine. This is the #1 correctness bug — verify your counting sort preserves relative order before trusting a multi-digit radix sort built on top of it.
• Ignoring the memory cost of a large k in counting sort. k on the order of the input's value range, not its size — sorting 100 elements with values up to 10^9 with plain counting sort allocates a billion-entry array for no benefit; that's exactly the signal to move to radix sort instead.
• Claiming these "beat" the comparison-sort lower bound. They don't contradict it — they operate outside the model the bound applies to (they use more information than pairwise comparisons). Getting this distinction right, out loud, is a strong signal of real understanding versus memorized trivia.

How to talk about this in an interview

"If the keys are bounded integers, I can beat the O(n log n) comparison-sort lower bound with counting or radix sort, since they use the key's actual value instead of pairwise comparisons — for a fixed-width 32-bit integer, radix sort is effectively O(n). That's not a contradiction of the n log n lower bound; that bound only applies to algorithms that decide order purely by comparison, and this one doesn't."

Beyond a coding round: sorting when the data doesn't fit in memory at all

Everything in this topic so far assumes the input fits in RAM. Real storage engines can't make that assumption — a database's ORDER BY on a result set larger than its configured memory budget, or a MapReduce job sorting terabytes across machines, both fall back to external merge sort: sort fixed-size chunks that fit in memory, write each to disk, then k-way-merge them back together (the exact min-heap-of-k-pointers pattern from Heaps' K-Way Merge, just backed by files instead of arrays). That's production storage-engine territory rather than something you implement from scratch in a coding round, so it's covered at the appropriate depth in the Databases roadmap's External Sort & Large Queries subtopic, including the concrete PostgreSQL work_mem and MapReduce shuffle-phase case studies.