Radix Sort

Idea

Radix sort is a non-comparison integer sort: split numbers by digit, stably sort by each digit (often counting/bucket sort) from least significant to most significant to get an ordered list.

The idea is worth pausing on, because it does something the rest of this course cannot. Every other sort you have met decides the order by comparing two elements. Radix sort never compares two elements at all. It decides the order by looking at one digit position at a time, sorting the whole array by that position, then moving to the next position. Because it does not compare, it is not bound by the $O(n \log n)$ limit that comparisons impose.

The price is that radix sort only works on keys you can take apart into digits — integers, or fixed-length strings — and the number of passes grows with the number of digits. For integers, each pass is a counting sort, and the whole thing runs in linear time in the number of elements.

Algorithm

1. Find max digit length $d$.
2. From LSD to MSD, stably sort by each digit (e.g., counting sort).
3. After $d$ passes, the array is sorted.

Pseudo-code:

function radixSort(A, d):
    for i = 1 to d:
        stably sort A by digit i (e.g., counting sort)

The word doing the work in step 2 is stably. A sort is stable when elements that compare equal keep their previous relative order. Stability is what makes the whole method work: after sorting by the ones digit, the tens-digit pass must not disturb the order that the ones-digit pass established. If a pass is not stable, the digits can end up in the wrong relative order — for example, sorting 170 and 75 by the tens digit while ignoring that 170 should come first because of its ones digit.

Implementation

The inner routine is a counting sort restricted to one digit position. The parameter exp selects the position: exp = 1 is the ones digit, exp = 10 the tens digit, and so on.

// Counting sort restricted to one digit position.
// exp = 1 selects the ones digit, exp = 10 the tens digit, and so on.
void CountSortByDigit(int A[], int n, int exp) {
    int output[n];
    int count[10] = {0};
    for (int i = 0; i < n; i++)
        count[(A[i] / exp) % 10]++;   // tally the digits at this position
    for (int i = 1; i < 10; i++)
        count[i] += count[i - 1];     // turn the histogram into prefix sums
    for (int i = n - 1; i >= 0; i--) {
        int digit = (A[i] / exp) % 10;
        output[count[digit] - 1] = A[i];  // stable placement
        count[digit]--;
    }
    for (int i = 0; i < n; i++) A[i] = output[i];
}

void RadixSort(int A[], int n) {
    int max = A[0];
    for (int i = 1; i < n; i++)
        if (A[i] > max) max = A[i];
    for (int exp = 1; max / exp > 0; exp *= 10)
        CountSortByDigit(A, n, exp);  // from the least significant digit up
}

Three details in that code carry the whole algorithm:

• count is a prefix sum, not a histogram. After the accumulation loop, count[d] holds the number of elements whose digit is at most d. Placing an element at output[count[digit] - 1] and then decrementing count[digit] walks each bucket from the back.
• The output loop runs backwards. Filling the buckets from i = n - 1 down to 0 is what makes the sort stable: elements that share a digit are written in their original relative order.
• max / exp > 0 decides when to stop. The loop ends as soon as exp exceeds the number of digits of the largest element, so a single pass is wasted at most.

Radix sort compared with counting sort and bucket sort

All three are non-comparison sorts, and all three therefore break the $O(n \log n)$ lower bound that applies to comparison sorts:

Radix sort is in essence multiple passes of counting sort, using stability to accumulate the ordering from the low digit to the high digit. The variables differ: for counting sort $k$ is the range of the keys, for bucket sort $k$ is the number of buckets, and for radix sort $r$ is the radix (the number of possible values per digit) and $d$ is the number of digits.

The practical consequence is a different kind of scaling. Counting sort degrades as the key range grows; radix sort stays linear in $n$ but pays $d$ passes, so it degrades with the length of the keys rather than their range. That is what makes radix sort the right choice for fixed-width identifiers such as timestamps or hashed values, and the wrong choice for arbitrary-length decimal strings.

Complexity

• Best/worst/avg: $O(d(n+r))$, with $d$ digits and radix $r$
• Space: $O(n+r)$
• Stability: stable

Note that the bound is the same for the best and the worst case. There is no “lucky” input that sorts faster, because the number of passes is decided by the number of digits of the largest element, not by how ordered the data already is. For the same reason the algorithm is not adaptive: giving it nearly sorted data buys nothing.

Exercises

Exercise 1

Run radix sort on $A = [170, 45, 75, 90, 802, 24, 2, 66]$; show results after each digit.

Exercise 2

What are radix sort’s time and space complexities?