Radix sort

Sort ten three-digit numbers by their last digit first, then by the middle one, then by the first. It seems backwards. Watch the third pass finish the job.

⋯5static void sort_by_digit(int *a, int *tmp, int n, int exp)6{7    int count[10] = { 0 };8    for (int i = 0; i < n; i++)9        count[(a[i] / exp) % 10]++;10    for (int d = 1; d < 10; d++)11        count[d] += count[d - 1];12    for (int i = n - 1; i >= 0; i--) {13        int d = (a[i] / exp) % 10;14        count[d]--;15        tmp[count[d]] = a[i];16    }17    for (int i = 0; i < n; i++)18        a[i] = tmp[i];19}20 21int main(void)22{23    int a[N] = { 512, 307, 845, 120, 693, 251, 718, 406, 934, 165 };24    int tmp[N];25    for (int exp = 1; exp <= 100; exp *= 10) {26        sort_by_digit(a, tmp, N, exp);27        for (int i = 0; i < N; i++)28            printf("%d ", a[i]);29        printf("\n");30    }31    return 0;

Last digit first

Each pass is a Counting sort on one decimal digit: count the digits, take running totals, place the numbers from the right into tmp, copy back. Because counting sort places from the right, each pass is stable: numbers with the same digit keep the order they came in.

That is why the last digit goes first. After the units pass, the numbers are in order of their units. The tens pass sorts them by tens, and among numbers with the same tens digit it keeps the units order, so the numbers are now in order of their last two digits. The hundreds pass does the same for all three digits. Each pass must be stable, or it would throw away the order the earlier passes built.

The code and its cost

static void sort_by_digit(int *a, int *tmp, int n, int exp)
{
    int count[10] = { 0 };
    for (int i = 0; i < n; i++)
        count[(a[i] / exp) % 10]++;
    for (int d = 1; d < 10; d++)
        count[d] += count[d - 1];
    for (int i = n - 1; i >= 0; i--) {
        int d = (a[i] / exp) % 10;
        count[d]--;
        tmp[count[d]] = a[i];
    }
    for (int i = 0; i < n; i++)
        a[i] = tmp[i];
}

(a[i] / exp) % 10 is the digit: with exp = 1 the units, 10 the tens, 100 the hundreds. main calls sort_by_digit for exp = 1, 10 and 100, and prints a after each pass:

120 251 512 693 934 845 165 406 307 718
406 307 512 718 120 934 845 251 165 693
120 165 251 307 406 512 693 718 845 934

Look at 120 and 165 in the last pass. Both have hundreds digit 1, so the hundreds pass cannot tell them apart; it keeps them in the order the tens pass left them, where 120 (tens digit 2) came before 165 (tens digit 6).

A pass costs n steps for each of its loops over the numbers and b for each loop over the digits. With d digits in base b, the whole sort is O(d(n + b)). For a fixed number of digits that is linear in n, and no key is ever compared with another.

Bases and the other direction

The base need not be 10. Base 256 sorts unsigned 32-bit integers in 4 passes (signed ones need their sign bit flipped first, so that negatives come before positives), one byte each, with 256 counters a pass; the digit is (x >> (8 * p)) & 0xFF. A larger base means fewer passes but more counters.

The most-significant-digit variant goes the other way: deal by the first digit into bins, then sort each bin separately and recursively by the next digit. It can stop as soon as a bin holds one item, and it suits strings, whose first characters usually decide the order.

Worked example

An unstable last pass. Suppose the hundreds pass placed numbers with equal digits in any order. 120 and 165 both have hundreds digit 1, so 165 could land before 120, and the result would be wrong even though every number is in the right bin.

A million 32-bit keys. In base 256: 4 passes × (10⁶ + 256) steps ≈ 4 × 10⁶. A good comparison sort needs about n log₂ n ≈ 2 × 10⁷ comparisons.

Two checks. How many passes for six-digit numbers in base 10? (6.) In base 1,000? (2.)

Where it’s used

Large arrays of integer keys, where a few byte passes beat comparisons.

Strings of a fixed length, such as codes and dates written as digits, one character per pass from the right.

Graphics, which sorts thousands of objects by their depth every frame.

Reference card

Platform: C11, gcc on x86-64 Linux: int 4 bytes, pointers 8, little-endian. Addresses in the pictures are short stand-ins, by one rule for the whole course; sizes are the real ones.