Radix Sort

By Victor Arce

Counting sort is fast, but it needs a small value range — one bin per possible value. For 32-bit integers that's billions of bins, which is hopeless. Radix sort sidesteps this: instead of one bin per value, it uses just ten bins, one per digit, and sorts the numbers one digit at a time.

The trick is the order. Radix sort goes least significant digit first — units, then tens, then hundreds — and each pass is a stable counting pass. Because each pass preserves the order set by the previous one, after the last digit the whole array is sorted. Step through it below with two-digit numbers (0–99), so there are two passes. Toggle show log to follow along.

How it works

Each pass is exactly one counting sort, keyed on a single digit:

1. Distribute. Walk the input; for each number, look at the current digit and drop the number into that digit's bin (0..9). On the first pass that's the units digit, on the next the tens digit.
2. Collect. Sweep the bins 0 → 9 back into the array. Items keep their arrival order inside a bin, so the pass is stableStable: equal values keep their original relative order after sorting..
3. Repeat for the next digit, feeding the collected array back in as the input.

Stability is the whole game. When the tens pass groups numbers by their tens digit, ties (same tens digit) stay in the order the units pass left them — so they're already sorted by units. Sort the least significant digit first and each later pass refines the order without disturbing the work below it.

Cost

With n numbers of d digits each in base k (here k = 10), radix sort runs in O(d · (n + k)) time — one O(n + k) counting pass per digit. When d and k are fixed (e.g. sorting 32-bit integers in fixed-width chunks), that's effectively linear in n, beating the Ω(n log n) comparison-sort bound for the same reason counting sort does: it never compares two numbers. The cost is the extra O(n + k) space for the bins, and the requirement that keys decompose into a small, fixed alphabet of digits.

Back to Sorting Algorithms