Radix Sort — Digit-Based Sorting

Imagine you're a postal worker in a large sorting facility, tasked with organizing thousands of letters by their ZIP codes. You could compare each pair of letters and gradually build a sorted pile—but that's not how postal services actually work. Instead, they use sorting bins: first separating letters by the first digit of the ZIP code, then by the second digit, and so on.

This intuitive approach—sorting by individual digits rather than comparing complete values—is the fundamental insight behind radix sort, one of the most elegant and powerful sorting algorithms ever devised. While comparison-based algorithms like merge sort and quicksort are bound by the O(n log n) lower bound, radix sort sidesteps this limitation entirely by exploiting the structure of the data rather than just comparing values.

To understand radix sort, we must first shift our perspective on what numbers actually are. When we write the number 4271, we typically think of it as a single atomic value—four thousand two hundred seventy-one. But this number is also a sequence of symbols: [4, 2, 7, 1], where each symbol comes from a finite alphabet (digits 0-9).

The key insight: If we can sort numbers by looking at one digit position at a time—and do so in a way that respects previous sorting decisions—we can sort the entire collection without ever directly comparing two complete numbers.

This is fundamentally different from comparison-based sorting:

Why does positional notation matter?

In our decimal system, the position of a digit determines its contribution to the value:

4271 = 4×10³ + 2×10² + 7×10¹ + 1×10⁰
     = 4000  +  200  +  70   +  1

Critically, the leftmost digits contribute more to the value than rightmost digits. This means:

• If two numbers differ in their leftmost digit, we know their relative order without examining other digits
• If two numbers share the same leftmost digit, their relative order depends on subsequent digits

Radix sort exploits this positional structure systematically, processing digits in a specific order to ensure correctness.

Given that numbers are sequences of digits, a natural question arises: in what order should we process the digits? There are two fundamental approaches, each with distinct characteristics:

1. Least Significant Digit First (LSD Radix Sort): Start from the rightmost digit and work toward the leftmost
2. Most Significant Digit First (MSD Radix Sort): Start from the leftmost digit and work toward the rightmost

Remarkably, both approaches can produce correct sorted output—but they work in fundamentally different ways and have different properties.

The stability imperative for LSD:

LSD radix sort has a crucial requirement that MSD does not: each pass must use a stable sorting algorithm. A sorting algorithm is stable if it preserves the relative order of elements with equal keys.

Why does LSD require stability? Consider what happens after multiple passes:

1. After sorting by the 1s digit, all numbers ending in 0 come first, then those ending in 1, etc.
2. When we then sort by the 10s digit, numbers with the same 10s digit must remain in their order from step 1
3. This ensures that 23 comes before 25 (same 10s digit, but 3 < 5 in 1s digit, established in step 1)

Without stability, earlier sorting decisions would be destroyed by later passes, producing incorrect results.

LSD radix sort is the more common variant, particularly for fixed-length integer sorting. Its elegance lies in its simplicity: perform d passes (one for each digit position), using a stable sort for each pass.

Algorithm Overview:

LSD_RADIX_SORT(array, d):
    for digit_position = 0 to d-1:    // 0 is rightmost
        STABLE_SORT(array by digit at position digit_position)
    return array

Let's trace through a complete example to build deep intuition.

Comprehensive Example:

Consider sorting the following 3-digit numbers:

Initial array: [329, 457, 657, 839, 436, 720, 355]

Pass 1: Sort by 1s digit (rightmost)

We extract the 1s digit of each number and group accordingly:

329 → digit 9
457 → digit 7
657 → digit 7
839 → digit 9
436 → digit 6
720 → digit 0
355 → digit 5

After stable sorting by this digit:

[720, 355, 436, 457, 657, 329, 839]
  0    5    6    7    7    9    9

Note: 457 appears before 657 (both have digit 7), preserving their original relative order. Similarly, 329 appears before 839 (both have digit 9).

Pass 2: Sort by 10s digit

Now we sort by the 10s digit, maintaining the order from Pass 1:

720 → digit 2
355 → digit 5
436 → digit 3
457 → digit 5
657 → digit 5
329 → digit 2
839 → digit 3

After stable sorting by this digit:

[720, 329, 436, 839, 355, 457, 657]
  2    2    3    3    5    5    5

Critical observation: Among numbers with 10s digit 2, 720 comes before 329. WHY? Because in Pass 1, 720 (ending in 0) was placed before 329 (ending in 9). The stable sort preserved this relative order.

Similarly, 355 < 457 < 657 because their 1s digits (5, 7, 7) were established in Pass 1, and among 457 and 657 (same 1s digit), their original order was preserved.

Pass 3: Sort by 100s digit (leftmost)

Final pass sorts by the most significant digit:

720 → digit 7
329 → digit 3
436 → digit 4
839 → digit 8
355 → digit 3
457 → digit 4
657 → digit 6

After stable sorting:

[329, 355, 436, 457, 657, 720, 839]
  3    3    4    4    6    7    8

The array is now completely sorted!

Notice that 329 < 355 (same 100s digit, but 29 < 55 established by earlier passes) and 436 < 457 (same 100s digit, but 36 < 57). The cumulative effect of stable sorting at each position builds up the correct total ordering.

MSD radix sort works in the opposite direction, processing from the most significant digit first. This approach is more similar to how a human might sort: first group by the leading digit, then within each group, sort by the next digit, and so on.

Algorithm Overview:

MSD_RADIX_SORT(array, digit_position, start, end):
    if start >= end or digit_position > max_digits:
        return
    
    // Partition array[start:end] into buckets by current digit
    buckets = PARTITION_BY_DIGIT(array, start, end, digit_position)
    
    // Recursively sort each bucket
    for each bucket in buckets:
        MSD_RADIX_SORT(bucket, digit_position + 1, bucket.start, bucket.end)

Example: MSD Radix Sort in Action

Initial array: [329, 457, 657, 839, 436, 720, 355]

Pass 1: Partition by 100s digit (leftmost)

Digit 3: [329, 355]
Digit 4: [457, 436]
Digit 6: [657]
Digit 7: [720]
Digit 8: [839]

Pass 2: Recursively sort each bucket by 10s digit

Bucket [329, 355] → sorted by 10s digit:

• 329 has 10s digit 2
• 355 has 10s digit 5
• Result: [329, 355] ✓

Bucket [457, 436] → sorted by 10s digit:

• 457 has 10s digit 5
• 436 has 10s digit 3
• Result: [436, 457] ✓

Single-element buckets [657], [720], [839] are already sorted.

Final result after concatenation:

[329, 355, 436, 457, 657, 720, 839] ✓

When to choose MSD over LSD:

1. Variable-length strings: MSD naturally handles strings of different lengths. "cat" and "category" can be sorted without padding because once we reach the end of "cat", it's placed before any longer string sharing that prefix.

2. Partially sorted output needed: MSD can provide lazy evaluation—you can get the smallest k elements without fully sorting the array.

3. High-entropy leading digits: When the most significant digits effectively separate the data into small buckets, MSD can terminate early.

4. Parallelizable workloads: Independent buckets after the first pass can be sorted in parallel.

Understanding why radix sort works—not just that it works—requires examining the mathematical invariants that guarantee correctness.

Theorem (LSD Radix Sort Correctness):

Given an array of numbers where each number has at most d digits, LSD radix sort using a stable sort at each digit position produces a correctly sorted array.

Proof by induction on the number of passes:

Base case (k=1): After one pass (sorting by the 1s digit), the array is correctly sorted if we only consider the 1s digit. All numbers ending in 0 precede those ending in 1, etc.

Inductive step: Assume after k passes, the array is correctly sorted with respect to the k least significant digits. Consider what happens in pass k+1 (sorting by digit position k+1):

• Numbers with different digits at position k+1 are correctly ordered by that digit
• Numbers with the same digit at position k+1 maintain their relative order from before this pass (by stability)
• By the inductive hypothesis, that relative order was correct for the k-digit suffix

Therefore, after pass k+1, the array is correctly sorted with respect to the (k+1) least significant digits. ∎

Why does MSD work differently?

MSD correctness relies on a different principle: divide-and-conquer with lexicographic ordering.

1. After partitioning by the first digit, all numbers starting with 1 come before those starting with 2, etc. This is globally correct because the first digit has the highest weight.

2. Within each partition, the first digit is constant. The relative order of numbers within a partition depends only on their remaining digits (positions 2 through d).

3. Recursively sorting each partition solves independent subproblems, eventually reaching single elements or examining all digits.

The key insight: MSD is correct because higher-order digits dominate lower-order digits in determining value. Once we partition by digit k, numbers in different partitions have their relative order fixed forever.

Moving from algorithm description to practical implementation requires addressing several key details:

Extracting digits efficiently:

For base-10 numbers, extracting the digit at position p:

digit = (number / 10^p) % 10

For base-2^k (binary, octal, hexadecimal), use bit manipulation:

digit = (number >> (k * p)) & ((1 << k) - 1)

The second form is significantly faster because division and modulo by powers of 2 are simple bit operations.

Why base 256?

Using base 256 (2⁸) instead of base 10 offers multiple advantages:

1. Fewer passes: 32-bit integers require only 4 passes in base-256 vs 10 passes in base-10 (for 10-digit numbers)
2. Efficient extraction: Bit shifting and masking are single-cycle operations on modern CPUs
3. Cache-friendly counts: 256-element count arrays fit comfortably in L1 cache
4. Power-of-two alignment: Computer memory and arithmetic are optimized for powers of 2

The trade-off is a larger count array (256 vs 10 elements), but this is negligible for modern systems.

A visual trace helps solidify understanding of how LSD radix sort progressively builds the sorted order. Let's trace through sorting [170, 045, 075, 090, 002, 024, 802, 066] with base 10:

We've explored the fundamental principles of radix sort—a powerful technique that escapes comparison-based sorting's lower bounds by exploiting the structure of positional numeral representations.

What's next:

Now that we understand the fundamental mechanism of radix sort—processing digits one position at a time—we'll examine how radix sort uses counting sort as a subroutine. This stable, linear-time sorting algorithm is the engine that powers each pass of radix sort, and understanding it deeply reveals why radix sort achieves its remarkable performance characteristics.