Radix sort, explained

Radix sort also avoids comparing whole numbers. It sorts by the last digit first, then by the next digit, and so on until the first digit.

Each digit pass must be stable, which means numbers with the same digit keep the order they had before. That is what makes the final result correct.

How it works

• Sort the numbers by their last digit, keeping the order of equal digits.
• Sort the result by the next digit to the left, again keeping the order of equal digits.
• Repeat for every digit position.
• After the leftmost digit, the list is fully sorted.

A small example

Sort this list:

53 7 91 24 68 35

By last digit:   91 53 24 35 7 68
By tens digit:   7 24 35 53 68 91

What to know about its cost

• O(d · (n + b)) time, where d is the number of digits and b is the base (10 for ordinary numbers).
• Needs O(n + b) extra space.
• Stable when each digit pass is stable.

Where it works well

• Fast for long lists of numbers with few digits.
• No direct comparisons between numbers.

Where it struggles

• Needs numbers (or fixed-length keys) that can be split into digits.
• Needs extra memory for each pass.

Try it yourself

Open the Sorting experiment, enter a list of two-digit numbers such as 53 7 91 24 68 35, choose Radix Sort and step through it. Then use the comparison view to run another algorithm on the same list and compare the comparisons and swaps.

Open the Sorting experiment