Radix Sort

Radix sort is a non-comparison sorting algorithm that sorts numbers digit by digit. Instead of comparing entire values, it processes individual digits from the least significant digit (LSD) to the most significant digit (MSD), using a stable subroutine (usually counting sort) at each step.

Radix sort is especially effective for integers with a fixed number of digits and is commonly used in real-world systems where predictable performance is required.

Example Walk-through

Consider this array of non-negative integers:

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

We sort the numbers digit by digit, starting from the ones place, then tens, then hundreds.

Pass 1 - Ones place

Group numbers by their last digit:

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

Reassemble (preserving order within each group):

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

Pass 2 - Tens place

Group by the tens digit:

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

Reassemble:

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

Pass 3 - Hundreds place

Group by the hundreds digit:

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

Reassemble:

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

The list is now fully sorted.

Radix sort’s key idea is that sorting digits individually eventually produces a fully ordered list.

Rust Implementation

This implementation uses LSD radix sort with counting sort as the stable subroutine.

pub fn radix_sort(arr: &mut [usize]) {
    if arr.is_empty() {
        return;
    }

    let max_value = *arr.iter().max().unwrap();
    let mut exp = 1;

    // Process each digit
    while max_value / exp > 0 {
        counting_sort_by_digit(arr, exp);
        exp *= 10;
    }
}

fn counting_sort_by_digit(arr: &mut [usize], exp: usize) {
    let mut output = vec![0; arr.len()];
    let mut count = vec![0; 10];

    // Count occurrences of digits
    for &value in arr.iter() {
        let digit = (value / exp) % 10;
        count[digit] += 1;
    }

    // Convert count to prefix sums
    for i in 1..10 {
        count[i] += count[i - 1];
    }

    // Build output array (stable)
    for &value in arr.iter().rev() {
        let digit = (value / exp) % 10;
        count[digit] -= 1;
        output[count[digit]] = value;
    }

    // Copy back
    arr.copy_from_slice(&output);
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn it_sorts() {
        let mut input = vec![170, 45, 75, 90, 802, 24, 2, 66];
        radix_sort(&mut input);
        assert_eq!(input, vec![2, 24, 45, 66, 75, 90, 170, 802]);
    }
}

Example Usage

fn main() {
    let mut values = vec![121, 432, 564, 23, 1, 45, 788];
    radix_sort(&mut values);
    println!("{:?}", values); // [1, 23, 45, 121, 432, 564, 788]
}

Time and Space Complexity

Radix sort’s performance depends on the number of digits (d) and the base (k, here 10).

Space Complexity

When to Use Radix Sort

Radix sort works best when:

• Sorting integers or fixed-length strings
• The number of digits is small
• Stable sorting is required
• Predictable linear performance is desired

It is less suitable when:

• Numbers have many digits
• Memory usage must be minimal
• Data types are not easily digit-decomposed

Playground Links

Rust - Radix Sort