Radix Sort

#How does it work?

Radix sort sorts numbers digit by digit. The LSD (least significant digit first) variant used here sorts by the ones digit, then the tens, then the hundreds.

Each pass uses a stable sort, usually counting sort. Stability is essential: numbers with the same tens digit must keep the order they got from the ones pass.

After the last digit pass the numbers are fully sorted, and not a single comparison was made.

#Live animation

for exp = 1, 10, 100, … while exp <= max:
  digit(v) = (v / exp) mod 10
  stable counting sort of a by digit(v)
  // after the pass, a is sorted by its last digits

#Step by step

1. 01Find how many digits the largest number has.
2. 02Stably sort by the ones digit.
3. 03Stably sort by the tens digit.
4. 04Repeat for every digit of the largest number.
5. 05The array is sorted.

#Example code

The same algorithm in 8 languages. Every program is compiled, run and checked to print the same output.

def sort_by_digit(a: list[int], exp: int) -> list[int]:
    """One stable counting-sort pass by the digit at `exp` (1, 10, 100, ...)."""
    count = [0] * 10
    for v in a:
        count[(v // exp) % 10] += 1
    for d in range(1, 10):
        count[d] += count[d - 1]
    output = [0] * len(a)
    # From the right, so numbers with the same digit keep their order.
    for v in reversed(a):
        d = (v // exp) % 10
        count[d] -= 1
        output[count[d]] = v
    return output


def radix_sort(a: list[int]) -> list[int]:
    """LSD radix sort for non-negative integers: ones digit first, then tens, ..."""
    exp = 1
    while a and max(a) // exp > 0:
        a = sort_by_digit(a, exp)
        exp *= 10
    return a


print(*radix_sort([170, 45, 75, 90, 802, 24, 2, 66]))

#Complexity

d is the number of digits and b the base (10 here). With a fixed number of digits (e.g. 32-bit integers) the time is linear. With very long or very uneven keys d grows and the advantage shrinks.

#When to use it?

Can beat comparison sorts on many integers, fixed-length keys (postal codes, phone numbers, dates) or equal-length strings. Also popular for parallel sorting on GPUs.

#Practice

Log in to answer questions and save your progress.