Radix Sort

Overview

Radix sort sorts integers digit by digit, starting from the least significant digit (LSD). It uses a stable auxiliary sort (typically counting sort) on each digit position, proceeding from right to left. If each digit lies in the range $[0, k-1]$ and there are $d$ digits, the running time is $\Theta(d(n + k))$.

The algorithm relies critically on the stability of the per-digit sort: when we sort by a more significant digit, equal digits in that position preserve the ordering established by all less significant digits.

Algorithm (LSD Radix Sort)

for i = 1 to d:
    stably sort array A on digit i

Digit 1 is the least significant digit (units). Each pass uses counting sort with $k$ being the radix (base) of the digit — typically $k = 10$ for decimal or $k = 256$ for byte-based sorting.

Worked Example

Sort [170, 45, 75, 90, 802, 24, 2, 66] by decimal digits ($d = 3$, pad with leading zeros: [170, 045, 075, 090, 802, 024, 002, 066]).

Pass 1: Sort by units digit (digit 1) Sorting stably by the last digit groups by units: 170(0), 090(0), 802(2), 002(2), 024(4), 045(5), 075(5), 066(6).

Result: [170, 090, 802, 002, 024, 045, 075, 066]

Pass 2: Sort by tens digit (digit 2) Stable sort by tens digit: 802(0), 002(0), 024(2), 045(4), 066(6), 170(7), 075(7), 090(9).

Result: [802, 002, 024, 045, 066, 170, 075, 090]

Pass 3: Sort by hundreds digit (digit 3) Stable sort by hundreds: 002(0), 024(0), 045(0), 066(0), 075(0), 090(0), 170(1), 802(8).

Result: [2, 24, 45, 66, 75, 90, 170, 802]

Sorted. Notice that 170 and 075 both had tens digit 7; stability preserved their order from the units pass (0 before 5, so 170 before 75). Similarly, 802 and 002 both had hundreds digit 0; stability preserved the tens-digit ordering.

Why LSD Works

After pass 1, the array is sorted by the least significant digit. Pass 2 sorts by the next digit; because the sort is stable, when two elements have the same value in digit 2, they remain in the order determined by pass 1 (i.e. by digit 1). By induction, after $d$ passes the array is fully sorted.

If the per-digit sort were unstable, a later pass could scramble the ordering established by earlier passes. Stability is therefore essential to radix sort’s correctness.

Complexity Analysis

For $n$ numbers with $d$ digits each, using counting sort for each digit:

• Each counting sort pass: $\Theta(n + k)$
• $d$ passes: $\Theta(d(n + k))$

For 32-bit integers, choosing bytes as digits gives $d = 4$, $k = 256$. Then $\Theta(4(n + 256)) = \Theta(n)$. Radix sort is a linear-time sort for fixed-width integers.

Historical Note

Radix sort was used by Herman Hollerith in his 1890 US Census tabulating machine. Punch cards were physically sorted into bins (digit buckets) and gathered, one digit column at a time. The IBM 83 Card Sorter (1955) sorted 1000 cards per minute using the same principle.

Comparison with Other Linear Sorts

Sort	Assumption	Time
Counting sort	Keys in $[0, k]$, $k = O(n)$	$\Theta(n + k)$
Radix sort	$d$ digits, each $0..k-1$	$\Theta(d(n + k))$
Bucket sort	Uniform distribution in $[0, 1)$	$\Theta(n)$ average

Radix sort generalises counting sort to larger key ranges by treating keys as composed of smaller-range digits.

Summary

Property	Value
Type	Non-comparison, digit-by-digit sort
Worst-case time	$\Theta(d(n + k))$
Space	Depends on underlying stable sort
Stable	Yes (if digit sort is stable)
Practical for	Fixed-width integers, strings
Beats $\Omega(n \log n)$	Yes (not comparison-based)