Radix Sort

Radix sort sidesteps comparison-based limits by sorting integers one digit at a time, relying on a stable sub-sort at each digit position to build up the full ordering. The central insight is counterintuitive: sorting by the least significant digit first, then the next, and so on produces a correct global order — provided each per-digit sort is stable. Stability is the load-bearing constraint of the entire algorithm.

The algorithm handles integers with d digits in base k. Each of the d passes runs a counting sort over k buckets, costing O(n + k) per pass, for a total of O(d(n + k)).

Step-by-Step Trace

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

Three passes are needed (max value 802 has 3 digits). Base 10, so k = 10.

Pass 1 — sort by ones digit

ones digits: 170→0, 45→5, 75→5, 90→0, 802→2, 24→4, 2→2, 66→6

bucket 0: [170, 90]
bucket 2: [802, 2]
bucket 4: [24]
bucket 5: [45, 75]
bucket 6: [66]

after pass 1: [170, 90, 802, 2, 24, 45, 75, 66]

Pass 2 — sort by tens digit (stability preserves ones-digit order within each bucket)

tens digits: 170→7, 90→9, 802→0, 2→0, 24→2, 45→4, 75→7, 66→6

bucket 0: [802, 2]
bucket 2: [24]
bucket 4: [45]
bucket 6: [66]
bucket 7: [170, 75]
bucket 9: [90]

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

Pass 3 — sort by hundreds digit

hundreds digits: 802→8, 2→0, 24→0, 45→0, 66→0, 170→1, 75→0, 90→0

bucket 0: [2, 24, 45, 66, 75, 90]
bucket 1: [170]
bucket 8: [802]

after pass 3: [2, 24, 45, 66, 75, 90, 170, 802]  ✓

Notice how 2, 24, 45, 66, 75, 90 are in the correct relative order inside bucket 0 of pass 3. That order was established by passes 1 and 2 and preserved because every counting sort step is stable.

Naive Implementation

MSD (most significant digit first) radix sort processes the most significant digit first and recurses on each bucket. It is conceptually closer to alphabetical filing but is recursive and harder to implement correctly.

fn msd_radix_sort(data: &mut Vec<usize>, base: usize) {
    if data.len() <= 1 {
        return;
    }
    let max_val = *data.iter().max().unwrap_or(&0);
    let digits = if max_val == 0 {
        1
    } else {
        (max_val as f64).log(base as f64).floor() as u32 + 1
    };
    msd_sort(data, base, digits);
}
 
fn msd_sort(data: &mut Vec<usize>, base: usize, position: u32) {
    if data.len() <= 1 || position == 0 {
        return;
    }
    let divisor = base.pow(position - 1);
 
    // Scatter into per-digit buckets
    let mut buckets: Vec<Vec<usize>> = vec![Vec::new(); base];
    for &x in data.iter() {
        let digit = (x / divisor) % base;
        buckets[digit].push(x);
    }
 
    // Recurse on each bucket, then gather back
    let mut idx = 0;
    for bucket in &mut buckets {
        msd_sort(bucket, base, position - 1);
        for &val in bucket.iter() {
            data[idx] = val;
            idx += 1;
        }
    }
}
 
fn main() {
    let mut data = vec![170usize, 45, 75, 90, 802, 24, 2, 66];
    msd_radix_sort(&mut data, 10);
    println!("{:?}", data); // [2, 24, 45, 66, 75, 90, 170, 802]
}

MSD requires recursion and allocates fresh bucket vectors at every level. It is also harder to make stable without extra bookkeeping.

Optimized Implementation

LSD (least significant digit first) processes digits from right to left using a stable counting sort at each pass. It is iterative, cache-friendly, and the standard choice in practice.

fn counting_sort_by_digit(input: &[usize], base: usize, exp: usize) -> Vec<usize> {
    let n = input.len();
    let mut count = vec![0usize; base];
 
    // Tally occurrences of the digit at this position
    for &x in input {
        let digit = (x / exp) % base;
        count[digit] += 1;
    }
 
    // Prefix-sum: count[d] becomes the one-past-last output index for digit d
    for i in 1..base {
        count[i] += count[i - 1];
    }
 
    // Place right-to-left for stability
    let mut output = vec![0usize; n];
    for &x in input.iter().rev() {
        let digit = (x / exp) % base;
        count[digit] -= 1;
        output[count[digit]] = x;
    }
 
    output
}
 
fn lsd_radix_sort(data: &[usize], base: usize) -> Vec<usize> {
    if data.is_empty() {
        return vec![];
    }
 
    let max_val = *data.iter().max().unwrap();
    let mut current = data.to_vec();
    let mut exp = 1usize;
 
    // One stable counting-sort pass per digit position
    while max_val / exp > 0 {
        current = counting_sort_by_digit(&current, base, exp);
        exp *= base;
    }
 
    current
}
 
fn main() {
    let data = vec![170usize, 45, 75, 90, 802, 24, 2, 66];
    let sorted = lsd_radix_sort(&data, 10);
    println!("{:?}", sorted); // [2, 24, 45, 66, 75, 90, 170, 802]
}

Using base 256 instead of base 10 reduces the number of passes to at most 4 for 32-bit integers (since 256⁴ = 2³²), cutting roughly 60% of the work compared to base-10 for nine-digit numbers.

Time Complexity

For 32-bit integers with base 256: d = 4, k = 256, giving roughly 4(n + 256) — effectively O(n) for large n. The total work is linear in the number of elements when d and k are treated as constants.

Why stability is non-negotiable. After pass 1, the array is ordered by ones digit. Pass 2 must preserve that order within each tens-digit group, or the ones-digit work is destroyed. An unstable sort at any pass corrupts every previous pass's contribution. This is why the inner counting sort iterates right-to-left through the input.

Space Complexity

O(n + k): one output buffer of size n and one count array of size k, reused across all d passes. The d passes are sequential rather than simultaneous, so space does not multiply by d.