Radix Sort
Sort digit by digit with a stable pass per position — linear-time sorting for fixed-width keys.
Hands on Interactive visualization
Implementation Code
// LSD radix sort, base 10, for non-negative integers.
// (Handle negatives by offsetting with the min value first.)
export function radixSort(a: number[]): number[] {
if (a.length === 0) return a;
const max = Math.max(...a);
let buf = new Array<number>(a.length);
for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {
const counts = new Array<number>(10).fill(0);
for (const v of a) counts[Math.floor(v / exp) % 10]++;
// Prefix sums: counts[d] = index just past digit d's bucket.
for (let d = 1; d < 10; d++) counts[d] += counts[d - 1];
// Reverse scan keeps each pass stable — mandatory for LSD radix.
for (let i = a.length - 1; i >= 0; i--) {
const d = Math.floor(a[i] / exp) % 10;
buf[--counts[d]] = a[i];
}
for (let i = 0; i < a.length; i++) a[i] = buf[i];
}
return a;
}Big-O Complexity
d = digits per key, k = radix (bucket count). For fixed-width integers d and k are constants, making it effectively O(n).
In production When to use
Sorting massive volumes of fixed-width keys — 32/64-bit IDs, timestamps, IPv4 addresses — where d·n passes beat n log n comparisons once n is in the tens of millions.
Column stores and join engines radix-partition fixed-width key columns; radix-based partitioning is a standard building block in modern hash-join and sort implementations.
GPU radix sort is the de facto standard for particle depth ordering and building bounding-volume hierarchies from Morton codes — its counting passes parallelize almost perfectly.
Ordering packets, flows, or routing entries by fixed-width addresses and ports: byte-per-pass radix sort gives predictable linear throughput.
MSD radix sort and three-way radix quicksort are the classic algorithms for large sets of strings, examining each character at most once per key prefix.
Trade-offs Strengths & weaknesses
- Effectively linear time for fixed-width keys — asymptotically beats comparison sorts.
- Stable, inheriting stability from its counting-sort passes.
- No comparisons and no data-dependent branching in the hot loop.
- Deterministic throughput regardless of key distribution or input order.
- Counting passes vectorize and parallelize well — the GPU sorting champion.
- Only works on keys decomposable into digits: integers, fixed-width strings, bit-castable floats.
- O(n) auxiliary buffer plus per-pass count arrays — never in-place in practice.
- d full passes over the data hurt cache efficiency versus one quicksort pass structure.
- Loses to quicksort when keys are long relative to log n (few elements, wide keys).
- Signed and floating-point keys need bit tricks (sign flip / order-preserving transforms) that are easy to get wrong.
Intuition Mental model
The post office pigeonhole wall
Mail sorters order letters by ZIP code one digit at a time: distribute into ten pigeonholes by a digit, gather in order, repeat with the next digit — never comparing two letters directly.
- Distribute all letters into pigeonholes 0–9 by the last digit of the ZIP code.
- Gather the pigeonholes in order, carefully keeping each stack's internal order — that is stability.
- Redistribute by the next digit to the left; ties on this digit stay in the order the previous round produced.
- After one round per digit, the entire mailbag is sorted end to end.
- Total work: number of digits × one pass over every letter — no letter ever compared to another.
Prep Interview questions
Radix sort is O(d·n) and quicksort is O(n log n) — when does radix actually win?
Why must each digit pass be stable, and what breaks if it is not?
LSD vs MSD radix sort — when would you choose each?
How do you radix-sort signed integers or floats correctly?
Why is base 256 the usual choice over base 10?
Watch out Common bugs
Implementing the digit pass with an unstable sort (or a forward placement scan) destroys the ordering established by earlier digits — output looks almost sorted, and tests on small inputs may even pass.
Bit-shifting a two's-complement negative puts it above all positives. Either offset by min first, flip the sign bit, or bucket negatives separately and reverse.
Hardcoding 4 byte-passes for values that are 64-bit (or stopping at a fixed digit count in base 10) leaves high digits unsorted. Derive d from the maximum key.
Each digit pass needs fresh counts. Forgetting to reset the array between passes accumulates stale tallies and scatters elements out of bounds.
One screen Cheat sheet
Stable counting sort per digit, least significant digit first.
- Effectively O(n) for fixed-width integer keys — d and k are constants.
- Every digit pass must be stable or the algorithm is simply wrong.
- Base 256 (byte passes) is the practical choice: shift + mask, L1-resident counts.
- Negatives and floats need order-preserving bit transforms first.
- Wins over comparison sorts when d < log n — huge n, narrow keys.
- GPU-friendly: counting passes parallelize almost perfectly.