↩ 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 [];
const max = Math.max(...arr);
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.
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 nine Non-Comparison Sorts entries — short version: this one when the sort needs to stay stable or memory isn't the bottleneck.