Radix sort

The problem it solves

Counting sort is linear, but its table is as wide as the value range — sort 32-bit integers with it and you need four billion slots. Radix sort keeps the no-comparisons superpower while shrinking the table to something laughable: ten slots (or 256, in production). The move is to stop treating a number as one huge key and start treating it as a short string of digits, sorted one digit at a time with a small stable sort per digit.

That turns “sort a million 32-bit integers” — a classic systems interview prompt — into a handful of linear passes: with base 256, exactly four passes over the data with a 256-entry table, total O(4·n). No comparison sort can say that. The constraint it buys this with: keys must be fixed-width sequences of digits drawn from a small alphabet — integers, fixed-length strings, IP addresses, dates. Variable-length, unbounded, or compare-only keys put you back in n-log-n territory.

The counter in the title block makes the pitch concrete: passes × n writes, and the comparisons counter never moves.

The intuition — and where it breaks down

Sorting library index cards by a three-digit catalogue number, the old way: first deal all cards into ten piles by the last digit and re-stack the piles in order; then deal by the middle digit; then by the first. After the third deal the cards are fully sorted. The magic feels backwards — why start with the least significant digit? — and the answer is the heart of the algorithm: each later deal is coarser but stable, so cards that tie on the current digit stay in the order the previous deals earned. After the final deal, cards are grouped by the most significant digit, and within each group the earlier deals’ order — which is exactly the order of the remaining digits — survives intact.

Where the analogy breaks down: with physical cards, stability is automatic — you deal onto the top of a pile and pick up in order without thinking. In code, stability is a property you must supply, and the moment your per-digit sort reorders equal digits, the earlier passes’ work is silently destroyed and the final “sorted” array is garbage in a way small tests may not catch. The second break: card numbers all have three digits; real data is ragged, and radix sort handles that by conceptually left-padding with zeros — which is why pass count is set by the widest key, not the average one.

Loading…

A walkthrough you can check

Sort [170, 45, 75, 90, 802, 24, 2, 66] in base 10.

1. Units pass — deal by last digit, collect buckets 0→9: [170, 90, 802, 2, 24, 45, 75, 66]. Sorted by units only; 170 leads because 0 is the smallest unit digit present.
2. Tens pass — deal by middle digit, stably: [802, 2, 24, 45, 66, 170, 75, 90]. Look at 802 and 2: both have tens digit 0, and they kept their pass-1 order — that is stability doing its silent work.
3. Hundreds pass: [2, 24, 45, 66, 75, 90, 170, 802]. Done — three passes, because the widest value (802) has three digits.

Now the check worth doing by hand: after pass 2, verify the array is sorted by its last two digits — 02, 02, 24, 45, 66, 70, 75, 90. It is, and that “sorted by the last d digits” statement is the invariant the whole proof hangs on. The visualization’s mid-run prediction asks exactly this: one pass in, is the array sorted? The bars say no — grouped by units, chaotic in magnitude — and knowing why it must still be no is knowing the algorithm.

The invariant

After the pass for digit d, the array is sorted by its last d digits. Induction: trivially true before any pass (zero digits). For the step, assume it holds after pass d−1. Pass d deals into buckets by digit d — so afterwards the array is grouped in ascending digit-d order — and because the deal is stable, elements sharing a digit-d value keep their pre-pass order, which by hypothesis was ascending in the last d−1 digits. Ascending on digit d, ties broken ascending on the previous d−1 digits: that is precisely “sorted by the last d digits.”

Run the induction to the final pass and the array is sorted by all digits — sorted, full stop. Notice the proof used stability exactly once, and could not have finished without it. That is why “why must each pass be stable?” is the follow-up interviewers actually ask: the invariant is unprovable — and false — without it.

Complexity, derived

Each pass touches every element twice (deal into a bucket, collect back) plus walks the b buckets: O(n + b) per pass. With d passes: O(d · (n + b)) time, O(n + b) space for the buckets. For 32-bit integers in base 256, d = 4 and b = 256, giving O(4n + 1024) ≈ O(n) with honest constants.

The base is a dial, and turning it is a classic space-time trade. Base 2: 32 trivially-cheap passes. Base 256: 4 passes with a 256-slot table — the practical sweet spot, since a byte-wide digit extraction is one mask-and-shift. Base 2³²: one pass, four billion slots — which is just counting sort again, saying the two algorithms are ends of a single dial. Against comparison sorts: d·n beats n·log n when d < log n, i.e. when keys are short relative to how many there are. A million 32-bit keys: d = 4 versus log n ≈ 20 — radix wins by five-fold on operation count. A hundred million distinct arbitrary-length strings: d is the string length and the advantage can invert.

Input order is irrelevant — like counting sort, there is no best or worst case, only key width. The visualization’s counters read identically for sorted and reversed presets.

What people get wrong

• An unstable digit pass. The single fatal bug. Any per-digit sort that reorders equal digits breaks the induction; results look plausibly shuffled rather than obviously wrong, which makes it a vicious production bug.
• Deriving pass count from the wrong thing: it comes from the widest key (or fixed key width), never from n. An array of two 6-digit numbers takes six passes.
• MSD/LSD confusion: dealing most-significant-first without recursing into buckets does not sort — after grouping by the leading digit you must sort within groups, which is a different (recursive) algorithm. LSD’s whole charm is that it never needs to.
• Negative numbers: two’s-complement digits do not order negatives correctly. Split by sign, or offset by the minimum as the code here does, or flip the sign bit for the final pass.
• Calling it O(n) unconditionally: it is O(d·n), and d is only constant when key width is. Interviewers probe this; “linear for fixed-width keys” is the defensible sentence.

Implementation notes

The drawn version deals into ten JavaScript arrays and concatenates — the clearest form of “stable buckets”. Production implementations use the counting-sort machinery instead: one prefix-summed count table per pass, elements copied into a scratch array by output[count[digit]++], then the roles of input and scratch swap each pass. Same behaviour, no allocation churn.

Base 256 is standard for binary data: digit extraction is (x >> (8·pass)) & 0xFF, four passes for 32-bit keys, and the count table lives happily in L1 cache. For strings of equal length, treat each character position as a digit and run right-to-left — the classic LSD string sort, and the reason radix sort loves fixed-width IDs. A worthwhile micro-optimisation: before each pass, check whether all remaining digits are zero (max ÷ exp = 0) and stop early — the loop condition in the displayed code does exactly this, which is why 45 and 802 in the walkthrough cost three passes, not ten.

The memory story is the honest downside: LSD radix needs an O(n) scratch buffer, where quicksort and heapsort sort in place. When n is huge and memory is the constraint, that single allocation can decide the argument.

The follow-up questions

Why least-significant digit first? Because it lets every pass be a flat, full-array, stable deal, with the invariant “sorted by the last d digits” carrying all the state. Most-significant-first must recurse into each bucket separately — also a fine algorithm (MSD radix / burstsort), but structurally different and no longer a sequence of simple passes.

Why must each pass be stable? The correctness induction uses stability to preserve the previous passes’ order among equal current digits. Concretely: after the tens pass, 21 and 25 share tens digit 2, and only stability guarantees 21 still precedes 25 from the units pass.

How do you pick the base? Larger base, fewer passes, bigger tables. b = 256 for machine integers is the standard answer: byte extraction is free and the table is cache-resident. State the trade, then name the sweet spot.

Radix versus quicksort for a million integers? Radix: 4 passes, ~O(4n), no comparisons, but an O(n) buffer and integer-only. Quicksort: O(n log n) comparisons, in place, works on anything comparable. On raw throughput for bounded integers, well-implemented radix typically wins; the moment keys become arbitrary objects, it does not even enter.