Radix sort visualization

Radix sort is a sorting algorithm for whole numbers that sorts them one digit at a time, starting with the least significant digit, using a stable counting sort for each digit. It never compares two numbers. This is the LSD (least significant digit first) version.

How it works

1. Take the ones digit of every number and sort the numbers by it with counting sort, using the 10 possible digits as the range.
2. Do the same with the tens digit, then the hundreds digit, until the digit positions are used up. Here that is 3 passes, for numbers up to 999.
3. A number with fewer digits has 0 in the missing positions.

Time and space complexity

With d digit positions and k possible digit values (10 here), each pass is a counting sort that costs O(n + k). The d passes give O(d (n + k)), the same for every arrangement of the input.

• Time, best, average and worst: O(d (n + k)), where k is the number of digit values (10). The comparison count is always 0; the work is writes. For a fixed d it grows linearly with n.
• Space: O(n + k): a count array of k cells and an output array of n cells, reused by every pass. It is not in place.

A worked example

Sort 170, 45, 75, 90, 802, 24, 2. The lesson always runs 3 passes, so 45 is read as 045 and 2 as 002. In each pass the table lists the digit of every number in the current order, and the array after the stable counting sort on that digit.

Stability is visible in every pass. In pass 1, 170 and 90 both have the ones digit 0, and 170 stays in front because it was first. In pass 2, 170 and 75 both have the tens digit 7, and 170 stays in front of 75 because pass 1 had put it there. After pass 2 the array is ordered by its last two digits, and after pass 3 by all three. The run makes 0 comparisons and 141 writes: 47 for each of the 3 passes, the same count that counting sort makes on 7 values and k = 9.

Pseudocode

A holds n whole numbers of at most d digits. Each pass is the counting sort from the previous lesson, with the digit as the key, so k = 9. D and B have n cells and C has 10.

RADIX-SORT(A, d)
    place = 1
    for p = 1 to d
        for j = 0 to n - 1
            D[j] = floor(A[j] / place) mod 10
        let C[0..9] be zeros
        for j = 0 to n - 1
            C[D[j]] = C[D[j]] + 1
        for i = 1 to 9
            C[i] = C[i] + C[i - 1]
        for j = n - 1 downto 0
            C[D[j]] = C[D[j]] - 1
            B[C[D[j]]] = A[j]
        for i = 0 to n - 1
            A[i] = B[i]
        place = place * 10

The textbook version is shorter: for p from 1 to d, use a stable sort to sort A on digit p, with digit 1 as the lowest. The code above spells out that stable sort. The outer loop runs d times and each pass costs O(n + k).

Stability

Radix sort is stable, because each pass is stable. In fact it only works because of it: a pass that reversed equal digits would undo the order of the previous pass.

When to use it, and when not to

• Use it for many integers or fixed-length keys with few digit positions: ids, zip codes, dates.
• Avoid it on small arrays: three passes of counting cost more than a simple sort on a handful of values, as the race shows.
• Avoid it when keys are long, because d grows with the key.

Where it is used

• Card-sorting machines. Punched-card sorters could only look at one column at a time, so operators sorted a deck on the last column first and moved toward the first. CLRS and Knuth both trace radix sort back to these machines, and the order of the passes is the same as in this lesson.
• Fixed-length keys. Dates sorted by day, then month, then year are the textbook example. Identifiers, zip codes and the four bytes of an IPv4 address work the same way: each position is a digit, and d is small and fixed.
• Large arrays of machine integers. A 32-bit integer can be treated as 4 digits of 8 bits each, so k is 256 and d is 4. Four counting passes then sort the array in time proportional to n, with no comparison between values.

Variations and related ideas

This is the LSD version. The MSD version starts with the most significant digit and then sorts each group of equal digits on its own, which suits strings of different lengths but needs recursion. The digit does not have to be decimal: bytes (k = 256) mean fewer passes, at the cost of a larger count array. Each pass is a counting sort, and the counting sort vs radix sort page runs the two on the same inputs. For the comparison sorts, see merge sort vs radix sort and quick sort vs radix sort, and the Big-O guide for all the costs side by side.