↩ back to Non-Comparison Sorts
Counting sort is fast — O(n+k) — but
only when the key range k stays small. Sort a million values spread across the full
32-bit integer range and counting sort tries to allocate billions of mostly-empty buckets. Radix
sort fixes exactly this without giving up the non-comparison trick: instead of one counting-sort
pass keyed by the whole value, it runs several passes keyed by one digit at a
time — ones, then tens, then hundreds, and so on — starting from the least significant
digit. Each pass only ever needs 10 buckets (one per digit 0–9), no matter how large the
numbers get. The number of passes grows with the number of digits, not with the value range itself.
Enter a comma-separated list of non-negative integers (this demo caps values at 999 — three digits is enough to show every phase without a wall of passes). Step through each digit pass: the array is counted into 10 digit-buckets (0–9), those counts become a running total, then each element is placed into its pass output, scanned right-to-left. The array after each pass becomes the input to the next pass, working from the ones digit up to the most significant.
It isn't obvious that sorting by the least significant digit first should work at all —
you'd expect the most significant digit to matter more. The trick is that every pass is a
stable counting sort, and stability is what makes the
passes compose correctly. After the ones-digit pass, any two elements with the same ones digit are
in the right relative order for that digit. When the tens-digit pass runs next, elements
with the same tens digit keep whatever order they already had — which is exactly their correct
order by ones digit, since that's what the previous pass produced. By induction, after processing
digit position d, the array is correctly sorted with respect to the low d+1
digits taken together as one key. Once every digit has been processed, the whole array is sorted.
Try it above: after pass 1 (ones digit) on the default array, watch 170 and
90 group together (both end in 0) in their original relative order — that order is
what pass 2 depends on.
Runs counting sort once per digit, least significant first, reusing the exact count → prefix-sum → place structure counting sort uses, just re-keyed by one digit instead of the whole value:
function radixSort(arr) {
if (arr.length === 0) return [];
let max = 0;
for (const v of arr) if (v > max) max = v; // not Math.max(...arr) — see Pitfalls
const numDigits = max === 0 ? 1 : Math.floor(Math.log10(max)) + 1;
let a = arr.slice();
for (let d = 0; d < numDigits; d++) {
const place = 10 ** d;
const buckets = new Array(10).fill(0);
for (const v of a) buckets[Math.floor(v / place) % 10]++; // count
for (let b = 1; b < 10; b++) buckets[b] += buckets[b - 1]; // prefix sum
const output = new Array(a.length);
for (let i = a.length - 1; i >= 0; i--) { // place, right to left
const digit = Math.floor(a[i] / place) % 10;
output[--buckets[digit]] = a[i];
}
a = output;
}
return a;
}
Every pass must be stable, or the whole sort breaks — not just the tie order.
With plain counting sort, an unstable placement pass still produces a correctly sorted array; only
equal elements swap relative order, a subtle bug but not a wrong answer. Radix sort has no such
safety net: each pass depends on the previous pass's relative order among ties, so a single
unstable pass can produce a final array that isn't sorted at all. Concretely, sort
[27, 15, 16] with an ones-digit pass first (fine — every ones digit here is distinct)
then a tens-digit pass that places left-to-right instead of right-to-left: 15 and
16 both have tens digit 1, and the unstable placement swaps them, producing
[16, 15, 27] — wrong, even though every individual pass "looked like" a correct
counting sort in isolation. Checked broadly, not just this one case: running every pass
left-to-right instead of right-to-left produces a wrong final order in roughly 70% of randomized
trials, not a rare edge case.
Only works directly on non-negative integers with a fixed digit width. Negative
numbers break digit extraction (Math.floor(v / place) % 10 doesn't mean the same thing
for negative v), so a real implementation needs an offset or a separate sign bucket —
this demo simply rejects negative input rather than adding that complexity. Non-integer keys (or
integers used as proxies for strings, dates, etc.) need to be mapped to a fixed-width digit
representation first.
The digit base (radix) is a real tuning knob. This demo uses base 10 for
readability — one digit maps to one buckets column a person can read at a glance. Production
implementations usually use base 256 (one byte at a time): a 32-bit integer always takes exactly 4
passes regardless of its value, each pass allocating 256 buckets instead of 10. Smaller base means
more passes but tinier buckets per pass; larger base means fewer passes but more buckets to
allocate and zero out every pass. Both extremes are still O(n)-ish for fixed-width
keys — the base only changes the constant, and that constant is measurable, not just directional;
see measuring the base trade-off below.
The classic Math.max(...arr) idiom has its own hidden array-size limit,
unrelated to how many digits a value has. Spreading an array into a function call pushes
every element onto the JS engine's call stack as a separate argument. The reference implementation
above used exactly that idiom until this fix — the same bug, in the same spread-into-a-function-call
shape, that counting sort's own reference
implementation shipped with and was fixed in session 487; it turned up again here while building
the benchmark below, this time on a page whose whole premise is handling values a plain comparison
sort struggles to key by efficiently at all. Fixed by computing max with a plain loop
instead of spread, which has no stack depth and no array-size ceiling.
The Pitfalls paragraph above reasons about base 10 versus base 256 by mechanism alone — more
passes with smaller buckets, or fewer passes with bigger ones — without ever running both. Measured
directly here: this page's own fixed radixSort above, parameterized by base, against
an otherwise-identical base-256 version, sorting arrays of 32-bit-range values (0 through
4,294,967,295, the fixed width the Complexity section below assumes) at sizes from 1,000 to
5,000,000 (correctness cross-checked against
Array.prototype.sort and against each other first, 0 mismatches across 500 random
trials).
Base 10 always needs 10 digit passes to cover that range (the largest 32-bit value,
4,294,967,295, has 10 decimal digits); base 256 always needs exactly 4 (4 bytes), regardless of
which values are actually present — both pass counts are fixed by the key width, never by the
data, exactly as the Complexity section's "d is a constant" claim says. That's a clean
2.5× difference in total elements touched across all passes (10 versus 4),
and wall-clock lands close to it but not exactly on it: roughly 2.1×–2.8×
faster for base 256 across that same size range, averaging around 2.3×–2.5×
over repeated runs in Node v20.20.2. The 256-slot bucket array costs measurably more to allocate
and zero per pass than the 10-slot one, but not enough to meaningfully eat into the win from paying
that cost 4 times instead of 10 — "the base only changes the constant" holds up, and for ordinary
fixed-width keys the constant favors the bigger base by a bit more than two times over, not just
"fewer passes" in the abstract.
Time: O(d·(n+k)) — d digit passes, each one a full
O(n+k) counting sort with k=10 (fixed, base 10). For fixed-width keys
(32-bit integers, say), d is a constant, so this is O(n) overall — genuinely
faster than any comparison sort's
Ω(n log n) floor, for the same reason
counting sort dodges it: this isn't a comparison sort
at all. Space: O(n+k) per pass (a 10-slot bucket array plus an
n-slot output array, reused each pass) — the same space profile as counting sort,
paid d times but not accumulated, since each pass's arrays are discarded before the
next begins. That per-pass output array isn't unavoidable: American flag sort processes the same kind of
fixed-width keys most-significant-digit first instead, and permutes values into their buckets
in place — trading this page's stability for an O(k)-per-level space bound instead
of O(n+k) per pass.
See Choosing a Non-Comparison Sort for how this compares against the site's other eleven Non-Comparison Sorts entries — short version: this one when the sort needs to stay stable or memory isn't the bottleneck.