Radix sort

Radix sort sorts integers (or fixed-length strings) by processing one digit at a time, from least significant to most significant (or vice versa). At each digit position, distribute elements into 10 buckets (one per digit value 0–9) using a stable sort like counting sort, then concatenate. After processing the most significant digit, the array is fully sorted.

Like Bucket sort, it doesn’t use comparisons — it exploits the structure of the data (integers as digits). Runs in $O(n)$ time per digit position, total $O(n\cdot d)$ where $d$ is the number of digits.

Algorithm (LSD = least-significant-digit first)

1. Find the maximum value in the array — this tells you how many digits to process.
2. For each digit position (1, 10, 100, …):
   • Count the occurrences of each digit (0–9).
   • Use the counts to determine each element’s output position.
   • Place each element in its output position. Stable order: elements with the same digit retain their relative order.
3. After processing the most significant digit, the array is sorted.

void radixsort(int array[], int size) {
    int max = getMax(array, size);
    for (int place = 1; max / place > 0; place *= 10) {
        countingSort(array, size, place);
    }
}

The countingSort helper sorts by a single digit position. It’s a stable Counting sort applied to the digit at the chosen place value (the iteration must be backward through the input to preserve stability — that’s what carries relative order across digit passes). For the full counting-sort algorithm and analysis, see Counting sort.

Big O

For $n$ elements with $d$ digits each:

• Each digit pass: $O(n+b)$ where $b$ is the radix (10 for decimal). Effectively $O(n)$ for fixed radix.
• Total: $O(d\cdot n)$.

When $d$ is constant (e.g., 32-bit integers), radix sort is $O(n)$ — faster than the $\Omega (n\log n)$ lower bound for comparison sorts.

Why it’s not comparison-based

The $\Omega (n\log n)$ lower bound applies only to algorithms that learn about the data through comparisons. Radix sort doesn’t compare values — it inspects digit positions directly. So the lower bound doesn’t apply.

The cost: radix sort only works on data that has digits to inspect. Floats, strings, custom objects with a comparison function — none of those are directly amenable. Radix sort can be adapted for fixed-length strings (process one character at a time), but for arbitrary objects, comparison sorts are still the standard.

When to use it

• Fixed-width integer keys. Network routing tables, sorting pixel intensities, sorting record IDs.
• Strings of bounded length. Phone numbers, ZIP codes.
• Very large datasets where the constant factor matters. Radix sort can outperform quicksort on integer arrays in practice.

LSD vs MSD

• LSD (least-significant-digit first): process the smallest digit first, work up to the largest. Standard form, easy to implement, requires processing all digits.
• MSD (most-significant-digit first): process the largest first, recurse on each bucket. Variable-length keys; can stop early if the data is determined sorted by a prefix. More complex.

Most descriptions (including this one) use LSD.

For the related distribution-based sort that uses ranges instead of digits, see Bucket sort.