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.

Bars of a list above a row of ten buckets labelled 0 to 9, a value dropping into the bucket for its last digit
Bars of a list above a row of ten buckets labelled 0 to 9, a value dropping into the bucket for its last digit

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.

A Hollerith punched-card tabulating machine at the Computer History Museum, of the kind used in the 1890 US census. Operators ran a deck through a sorter once per column, the ancestor of radix sort.
A Hollerith punched-card tabulating machine at the Computer History Museum, of the kind used in the 1890 US census. Operators ran a deck through a sorter once per column, the ancestor of radix sort.

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