Counting Sort and Radix Sort

Every algorithm textbook warns you: sorting n numbers by comparing them cannot do better than $O(n \log n)$ in the worst case. Merge sort, heapsort, and the best quicksort variants all live at that ceiling.

But what if you stop comparing?

Counting sort, invented in the early 1950s, exploits the fact that integers live in a bounded range. Instead of asking "is A bigger than B?", it asks "how many numbers equal each value?" then reconstructs the sorted order from those counts — in $O(n + k)$ time, where k is the size of the value range.

Radix sort goes further. It applies counting sort digit-by-digit — least significant digit first — sorting the array one digit position at a time. Each pass runs in $O(n + k)$, and with d digit positions the whole algorithm finishes in O(d · (n + k)). For fixed-width integers (e.g. 32-bit), d is constant, giving true linear time $O(n)$.

This is not a trick or a special case. It is a mathematically proven faster algorithm — proven possible because the $O(n \log n)$ lower bound only applies to comparison-based sorting. Once you exploit the structure of the keys, the barrier disappears.

The demo below sorts a shuffled list of three-digit numbers using LSD radix sort. Press Step to execute one digit pass (units → tens → hundreds) and watch the bars lock into place one digit at a time. Press Reset to shuffle and start again.

<p class="hint">{{hint}}</p>
<div id="pass-label" class="pass-label">{{pass_label_prefix}} <span id="pass-name">–</span></div>
<div id="bars" class="bars"></div>
<div id="digits-row" class="digits-row"></div>
<div class="status" id="status">{{status_initial}}</div>
<div class="btns">
  <button id="step" type="button">{{btn_step}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .8rem; line-height: 1.45; }
.pass-label { font-size: .85rem; font-weight: 600; color: #1d3557; margin-bottom: .4rem; min-height: 1.2em; }
.bars { display: flex; align-items: flex-end; gap: 5px; height: 180px; padding: 0 2px; }
.bar-wrap { display: flex; flex-direction: column; align-items: center; flex: 1; }
.bar { width: 100%; border-radius: 4px 4px 0 0; transition: height .35s, background .35s; }
.bar.highlighted { background: #e63946 !important; }
.bar-val { font-size: .72rem; font-weight: 700; color: #1d3557; margin-top: 3px; }
.digits-row { display: flex; gap: 5px; margin-top: 4px; padding: 0 2px; }
.digit-badge { flex: 1; text-align: center; font-size: .7rem; padding: 2px 0; border-radius: 4px;
               font-weight: 700; color: #fff; min-height: 1.4em; }
.status { font-size: .95rem; font-weight: 600; margin: .6rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.btns { display: flex; gap: .5rem; }
button { font: 600 14px system-ui; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .4; cursor: default; }

// Code not found

Notice how each pass produces a stable intermediate order: numbers that agree on the current digit keep their relative sequence from the previous pass. It is this stability that lets the final pass on the hundreds digit produce a fully sorted array — not luck, but a mathematical guarantee.

The Ω(n log n) lower bound for comparison-based sorting is one of the cleanest results in theoretical computer science. Its proof is information-theoretic:

• There are n! possible orderings of n distinct keys.
• Each comparison reveals at most 1 bit, ruling out half the remaining orderings.
• To distinguish all n! orderings you need at least $\log_{2}(n!)$ ≈ n log n comparisons.
• This is a provable lower bound — no comparison sort can escape it.

Counting sort sidesteps the bound entirely. It never compares two elements. Instead:

1. Allocate a count array of size k (the value range).
2. Tally how many times each value appears — $O(n + k)$.
3. Walk the count array to reconstruct the sorted output — $O(n + k)$.

Radix sort chains counting sorts across d digit positions, processing the least-significant digit first (LSD variant):

• Each pass is a stable $O(n + k)$ counting sort on one digit (k = 10 for decimal).
• After d passes the array is fully sorted in O(d · (n + k)).
• For 32-bit integers: d = 4 bytes, k = 256 → roughly 4 · (n + 256) — linear in n.

The catch: this advantage is real but conditional.

• k must be manageable. Sorting 64-bit arbitrary keys with k = $2^{64}$ buckets is impossible.
• The constants matter. For small n, the simpler $O(n \log n)$ sorts are faster in practice.
• Radix sort uses $O(n + k)$ extra space for the output buffer and count array.

The result is nonetheless striking: by treating keys as structured data rather than opaque values to compare, you can sort in provably sub-comparison time — a fact proven by Harold H. Seward (counting sort, 1954) and formalized across decades of algorithm analysis.

For contrast, see Sorting Lower Bounds for the full proof that comparison sorts cannot escape $O(n \log n)$, and Selection and the Median for another algorithm that beats naive expectations by exploiting structure.

Linear-time integer sorting is not just a theoretical curiosity — it sits at the heart of several critical systems:

• GPU rendering: sorting fragments by depth (z-buffer) is one of the most common operations in real-time 3D graphics. GPUs run radix sort on millions of fragments per frame because nothing faster exists.
• Suffix arrays: building the compressed index behind every modern search engine or DNA aligner requires sorting millions of suffixes. Radix-sort-based suffix array construction runs in $O(n)$ and is the practical gold standard.
• Network packet classification: routers classify billions of packets per second by IP address (a 32-bit integer). Counting-sort variants drive hardware packet schedulers.
• Database query processing: sorting integer foreign keys before a hash join is a common relational algebra operation; linear-time sorts cut a measurable fraction off query plans.
• Genome sequencing: k-mer counting (tallying short DNA substrings) is pure counting sort applied to an alphabet of size $4^{k}$, enabling assembly of gigabase genomes in linear passes.

Whenever your keys are integers with bounded range and n is large, the question is not whether to use radix sort — it is which variant and what radix to choose.

The $O(n \log n)$ barrier is real — but only for algorithms that learn about order by comparing pairs of elements. Counting sort and radix sort take a different path: they read the structure of the keys directly, replacing comparisons with counting passes over a bounded alphabet.

The payoff is real, provable linear time. Not an approximation, not an amortized average — a worst-case guarantee that no comparison sort can match.

That is the deeper lesson. Complexity lower bounds are always conditional: they hold within a model of computation. Step outside the comparison model — exploit what you actually know about the data — and barriers that seemed fundamental dissolve. Radix sort is one of the clearest examples of this principle in all of algorithm design.

To see the other side of the coin — the proof that comparison sorts truly cannot escape $O(n \log n)$ — visit Sorting Lower Bounds.