Radix Sort

Sort numbers one digit at a time from least-significant to most, using a stable pass each time. No comparisons.

Radix sort sorts numbers without ever comparing two of them. It orders them one digit at a time, starting from the rightmost (least-significant) digit and working left. Each pass is a stable bucketing by a single digit. The magic is that stability preserves the work of earlier passes, so after the last digit the whole list is sorted.

Why least-significant first works

It feels backwards to start with the ones digit, but stability is what makes it click. When a later pass sorts by the tens digit, two numbers with the same tens digit keep the order the previous (ones) pass gave them. So higher digits dominate, and within a tie the lower digits — already sorted — break it correctly.

input:        170  45  75  90  802  24  2  66

by 1s digit:  170  90  802  2  24  45  75  66
by 10s digit: 802  2  24  45  66  170  75  90
by 100s digit:  2  24  45  66  75  90  170  802   <- sorted

1Find the maximum value to know how many digit passes d you need.
2Starting at the ones digit, stably bucket all numbers by that digit (counting sort by digit).
3Move to the next digit left and repeat the stable bucketing.
4After the most-significant digit, the list is fully sorted.

The stable pass is non-negotiable

If any digit pass were unstable, it would scramble the order established by earlier passes and the result would be wrong. Each pass is almost always a counting sort on that one digit — precisely because counting sort is stable and runs in linear time.

Reading the cost

Each of the d passes is an O(n + k) counting sort, where k is the base (10 for decimal digits). Total time is O(d · (n + k)). For fixed-width numbers d is a constant, so radix sort is effectively linear in n.

OperationTimeSpace

All cases · d digits, base k; one stable pass per digitO(d · (n + k))O(n + k)

Check yourself

Why must each digit pass in LSD radix sort be stable?