Radix sort
Radix sort is the odd one out among sorting algorithms: it never asks which of two values is larger. It reads the numbers digit by digit and sorts them by one digit at a time, using ten buckets. The idea is older than computers: it is how punched-card sorting machines worked.
The idea
Sort the numbers by their ones digit only. Then sort them by their tens digit, but in a way that keeps numbers with the same tens digit in the order the first pass gave them. Then by the hundreds, the same way. After the last pass the list is sorted: the hundreds decide first, ties in the hundreds are already in order of their tens, and ties there in order of their ones.
One pass, with buckets
Each pass uses ten buckets, one for each digit 0 to 9. Go through the list from start to end and move every number into the bucket for its digit, behind the numbers already there. Then empty the buckets back into the list in order, bucket 0 first. Moving the numbers in list order and appending them to the back of a bucket is what keeps the pass stable. The app counts the numbers for each digit first, so the buckets can sit side by side in one row, each starting right after the one before it: that is a counting sort on one digit.
An example
Take 170, 45, 75, 90, 802, 24, 2, 66. By the ones digit: 170, 90, 802, 2, 24, 45, 75, 66. By the tens digit: 802, 2, 24, 45, 66, 170, 75, 90; note that 802 and 2, both with tens digit 0, keep their order from the first pass. By the hundreds digit: 2, 24, 45, 66, 75, 90, 170, 802. Three passes over eight numbers: 24 digits read and 48 moves, and not one comparison.
How fast is it?
Each pass reads one digit of every number and moves every number twice, so for n numbers with d digits the work grows with n · d. A comparison sort needs at least about n log₂ n comparisons in the worst case, because it has to tell n! possible orders apart one yes-or-no question at a time. Radix sort is not bound by that, since it never asks such questions. For many short keys, like a million numbers below 1,000, three passes are far less work than the roughly 20 million comparisons a comparison sort would need. For long keys or few values, the advantage disappears.
LSD and MSD, and history
The version shown here starts with the least significant digit (LSD). The other way round, most significant digit first (MSD), splits the list into buckets by the first digit and sorts each bucket separately, which suits strings of different lengths. Radix sorting goes back to the punched-card sorters that followed Herman Hollerith's tabulating machines of the 1890 US census: a sorter dropped each card into one of ten pockets by the hole in one column, and operators ran the deck through once per column, starting with the last.
Explore it
Open the app and press Step. Each pass first counts the digits, which marks out the buckets 0 to 9 in the row under the list. Then the numbers drop into their buckets one by one, the active bucket highlighted, and are copied back. Type your own numbers up to 999, such as the example above, to see all three passes.
Frequently asked questions
What is the time complexity of radix sort?
O(n · d) for n keys of d digits in a fixed base, plus the cost of the buckets for each pass. It needs O(n) extra memory for the buffer the buckets live in.
Is radix sort stable?
LSD radix sort has to be: it only works because every pass keeps values with the same digit in the order they came in. The final result is therefore stable too.
Can radix sort handle negative numbers or decimals?
Not directly, but it can with a trick: shift negative numbers so they are all positive, or sort them separately and reverse them. Floating-point numbers can be sorted by their bit patterns after a small transformation.
Why use base 10?
Because it is easy to follow. Computers usually sort by 8 or 16 bits at a time, so a 32-bit number takes four or two passes, with 256 or 65,536 buckets.
Ready to try it?
Open PictorX in your browser — no install, no credit card required to start.
Try radix sort