Radix Sort: One Stable Pass per Digit, Least Significant First

Radix sort is a sorting algorithm for keys made of digits: it sorts the items by one digit at a time, starting with the least significant, using a stable sort for each pass, and after the pass on the most significant digit the items are in order. This card covers the least-significant-digit version, why each pass has to be stable, and what the sort costs.

A key's digits are the positions of its value written in some base b, the number of different values a digit can take: base 10 gives the decimal digits, and base 256 splits an integer into bytes. Least-significant-digit radix sort, LSD radix sort for short, makes one pass per digit position, ones first, then tens, then hundreds, and each pass is a counting sort that uses the digit as its key. A digit has only b values, so each pass needs only b counters, however wide the whole key is.

The trace sorts 13 4 10 7 14 3 10 in base 10. The largest key has two digits, so there are two passes, and each frame shows the array after one.

After the ones pass, the array is sorted by its last digit only: 13 sits before 4, because 3 is smaller than 4. The tens pass then sorts by the first digit, and within each tens group the items keep the order the ones pass gave them. That is why the pass must be stable. When two keys share a tens digit, the tens pass cannot tell them apart, and the only thing that puts 13 before 14 is that the ones pass already did and the tens pass left them alone. An unstable pass could swap them, and the sort would be wrong with no error.

Sorting a pile of exam papers by surname works the same way if you do it backwards: sort by the third letter, then the second, then the first, keeping papers in their current order whenever letters tie. The analogy breaks on length. Surnames have different lengths, and LSD radix sort needs every key to have the same number of digits, so shorter keys are padded, with leading zeros for numbers.

Sorting by the most significant digit first and never looking back does not work this way. A pass on the tens digit groups 3 4 7 apart from 10 10 13 14, but a later pass on the ones digit would scatter the groups again. Radix sort that starts at the most significant digit exists, but it has to sort each group separately, recursively, which is a different algorithm.

The sign to reach for radix sort is keys with a fixed width that is too wide for counting sort: 32-bit or 64-bit integers, fixed-length codes, dates written as year, month and day. The base is a choice. A million 64-bit keys in base 256 take 8 passes, about 8 × (n + 256) = 8,002,048 steps, and in base 65,536 take 4 passes, about 4,262,144 steps, against roughly 20 million comparisons for an n log₂ n comparison sort; a step and a comparison do not cost the same, so measure before trusting the ratio.