Radix Sort Algorithm in DSA Rust

Mental Model

Radix sort sorts numbers by processing digits from least to most significant, grouping numbers by each digit step by step.

Analogy: Imagine sorting mail by zip code: first by the last digit, then the second last, and so on, until fully sorted.

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

Buckets for digits 0-9:
0: []
1: []
2: []
3: []
4: []
5: []
6: []
7: []
8: []
9: []

Dry Run Walkthrough

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

Goal: Sort the list in ascending order using radix sort

Step 1: Sort numbers by least significant digit (units place)

Buckets:
0: [170, 90]
1: []
2: [802, 2]
3: []
4: [24]
5: [45, 75]
6: [66]
7: []
8: []
9: []
Reassembled list: [170, 90, 802, 2, 24, 45, 75, 66]

Why: Grouping by units digit organizes numbers partially to prepare for next digit sorting

Step 2: Sort numbers by second least significant digit (tens place)

Buckets:
0: [802, 2]
1: []
2: [24]
3: []
4: [45]
5: []
6: [66]
7: [170, 75]
8: []
9: [90]
Reassembled list: [802, 2, 24, 45, 66, 170, 75, 90]

Why: Sorting by tens digit refines order further, grouping numbers by their tens place

Step 3: Sort numbers by third least significant digit (hundreds place)

Buckets:
0: [2, 24, 45, 66, 75, 90]
1: [170]
2: []
3: []
4: []
5: []
6: []
7: []
8: [802]
9: []
Reassembled list: [2, 24, 45, 66, 75, 90, 170, 802]

Why: Sorting by hundreds digit completes the sorting as all digits are processed

Result:

Final sorted list:
2 -> 24 -> 45 -> 66 -> 75 -> 90 -> 170 -> 802 -> null

Annotated Code

DSA Rust

use std::fmt::{self, Display, Formatter};

struct RadixSort {
    data: Vec<u32>,
}

impl RadixSort {
    fn new(data: Vec<u32>) -> Self {
        Self { data }
    }

    fn get_max(&self) -> u32 {
        *self.data.iter().max().unwrap_or(&0u32)
    }

    fn counting_sort(&mut self, exp: u32) {
        let n = self.data.len();
        let mut output = vec![0u32; n];
        let mut count = vec![0u32; 10];

        // Count occurrences of digits
        for &num in &self.data {
            let index = (num / exp) % 10;
            count[index as usize] += 1u32;
        }

        // Change count[i] so that it contains actual position
        for i in 1..10 {
            count[i] += count[i - 1];
        }

        // Build the output array
        for &num in self.data.iter().rev() {
            let index = (num / exp) % 10;
            count[index as usize] -= 1u32;
            output[count[index as usize] as usize] = num;
        }

        // Copy to data
        self.data = output;
    }

    fn radix_sort(&mut self) {
        let max = self.get_max();
        let mut exp = 1;
        while max / exp > 0 {
            self.counting_sort(exp);
            exp *= 10;
        }
    }
}

impl Display for RadixSort {
    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
        let s = self.data.iter().map(|n| n.to_string()).collect::<Vec<_>>().join(" -> ");
        write!(f, "{} -> null", s)
    }
}

fn main() {
    let mut sorter = RadixSort::new(vec![170, 45, 75, 90, 802, 24, 2, 66]);
    sorter.radix_sort();
    println!("{}", sorter);
}

for &num in &self.data { let index = (num / exp) % 10; count[index as usize] += 1u32; }

Count occurrences of current digit for all numbers

for i in 1..10 { count[i] += count[i - 1]; }

Accumulate counts to get positions for stable sorting

for &num in self.data.iter().rev() { let index = (num / exp) % 10; count[index as usize] -= 1u32; output[count[index as usize] as usize] = num; }

Place numbers into output array in stable order based on current digit

self.data = output;

Copy sorted output back to data for next digit pass

while max / exp > 0 { self.counting_sort(exp); exp *= 10; }

Repeat counting sort for each digit from least to most significant

Output

2 -> 24 -> 45 -> 66 -> 75 -> 90 -> 170 -> 802 -> null

Complexity Analysis

Time: O(d * (n + k)) where d is number of digits, n is number of elements, k=10 digits; because it sorts by each digit using counting sort

Space: O(n + k) for output and count arrays used in counting sort

vs Alternative: Compared to comparison sorts like quicksort O(n log n), radix sort can be faster for fixed digit sizes since it avoids comparisons

Edge Cases

Empty list

No sorting needed, output remains empty

DSA Rust

let max = self.get_max(); // unwrap_or handles empty by returning 0

List with one element

Sorting runs but no changes, returns the single element

DSA Rust

while max / exp > 0 { ... } // loop runs once or zero times safely

All elements are the same

Sorting runs but output remains unchanged

DSA Rust

counting_sort uses stable counting, so duplicates stay in order

When to Use This Pattern

When you need to sort integers or fixed-length strings efficiently without comparisons, reach for radix sort because it sorts digit by digit in linear time.

Common Mistakes

Mistake: Not using stable sorting for each digit pass, causing incorrect final order
Fix: Use counting sort in reverse order iteration to maintain stability

Mistake: Forgetting to process all digits up to the maximum number's length
Fix: Loop until max / exp is zero to cover all digit places

Summary

Sorts numbers by processing digits from least to most significant using stable counting sort.

Use when sorting integers or fixed-length data where comparison-based sorting is less efficient.

The key insight is sorting by each digit step-by-step preserves order and leads to a fully sorted list.

Practice

1. What is the main idea behind the Radix Sort Algorithm?

easy

A. Sort numbers by swapping adjacent elements repeatedly

B. Sort numbers by comparing each pair directly

C. Sort numbers by dividing them into two halves recursively

D. Sort numbers digit by digit starting from the least significant digit

Solution

1. Step 1: Understand Radix Sort approach

   Radix sort sorts numbers by processing each digit separately, starting from the least significant digit (rightmost).

2. Step 2: Compare with other sorting methods

   Unlike comparison-based sorts, radix sort uses digit positions to sort without direct element comparisons.

3. Final Answer:

   Sort numbers digit by digit starting from the least significant digit -> Option D

4. Quick Check:

   Radix sort = digit-by-digit sorting [OK]

Hint: Radix sort processes digits from right to left [OK]

Common Mistakes:

• Thinking radix sort compares elements directly
• Assuming it sorts by dividing arrays recursively
• Confusing it with bubble or quick sort methods

2. Which of the following Rust code snippets correctly initializes a vector to hold buckets for digits 0 to 9 in radix sort?

easy

A. let mut buckets: Vec = vec![Vec::new(); 10];

B. let buckets = Vec::with_capacity(10);

C. let buckets: Vec<i32> = vec![0; 10];

D. let mut buckets = vec![0; 10];

Solution

1. Step 1: Understand bucket structure needed

   Radix sort uses buckets as vectors of vectors to hold numbers for each digit (0-9).

2. Step 2: Check Rust syntax for initializing vector of vectors

   Using vec![Vec::new(); 10] creates 10 empty vectors, one for each digit bucket.

3. Final Answer:

   let mut buckets: Vec = vec![Vec::new(); 10]; -> Option A

4. Quick Check:

   Vector of vectors for buckets = let mut buckets: Vec = vec![Vec::new(); 10]; [OK]

Hint: Buckets need vectors inside a vector, not just integers [OK]

Common Mistakes:

• Using Vec<i32> instead of Vec for buckets
• Using with_capacity without initializing inner vectors
• Initializing buckets as integers instead of vectors

3. What will be the output of the following Rust code snippet implementing one pass of radix sort on the least significant digit?

let arr = vec![170, 45, 75, 90, 802, 24, 2, 66];
let mut buckets: Vec = vec![Vec::new(); 10];
for &num in &arr {
    let digit = num % 10;
    buckets[digit as usize].push(num);
}
let mut result = Vec::new();
for bucket in buckets {
    for num in bucket {
        result.push(num);
    }
}
println!("{:?}", result);

medium

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

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

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

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

Solution

1. Step 1: Calculate least significant digit for each number

   Digits: 170%10=0, 45%10=5, 75%10=5, 90%10=0, 802%10=2, 24%10=4, 2%10=2, 66%10=6.

2. Step 2: Place numbers in buckets and flatten

   Buckets: 0->[170,90], 2->[802,2], 4->[24], 5->[45,75], 6->[66]. Flattening in order: [170, 90, 802, 2, 24, 45, 75, 66].

3. Final Answer:

   [170, 90, 802, 2, 24, 45, 75, 66] -> Option B

4. Quick Check:

   Sorted by least digit = [170, 90, 802, 2, 24, 45, 75, 66] [OK]

Hint: Check digit % 10 and group accordingly [OK]

Common Mistakes:

• Mixing up digit extraction with division
• Not preserving order within buckets
• Incorrectly flattening buckets

4. Identify the bug in this Rust code snippet for one pass of radix sort and choose the fix:

let arr = vec![170, 45, 75];
let mut buckets: Vec = vec![Vec::new(); 10];
for num in arr {
    let digit = num / 10 % 10;
    buckets[digit].push(num);
}

medium

A. Change buckets[digit] to buckets[digit as usize]

B. Change num / 10 % 10 to num % 10

C. Initialize buckets with vec![0; 10] instead of vectors

D. Use for &num in &arr instead of for num in arr

Solution

1. Step 1: Identify type mismatch in indexing

   Variable digit is an integer but Rust requires usize for vector indexing.

2. Step 2: Fix by casting digit to usize

   Use buckets[digit as usize] to correctly index the vector.

3. Final Answer:

   Change buckets[digit] to buckets[digit as usize] -> Option A

4. Quick Check:

   Vector index must be usize = Change buckets[digit] to buckets[digit as usize] [OK]

Hint: Vector indices in Rust must be usize type [OK]

Common Mistakes:

• Using integer directly as vector index without casting
• Changing digit calculation unnecessarily
• Incorrect bucket initialization

5. Given the Rust function below that performs radix sort on a vector of positive integers, what will be the final sorted vector?

fn radix_sort(mut arr: Vec<i32>) -> Vec<i32> {
    let max = *arr.iter().max().unwrap();
    let mut exp = 1;
    while max / exp > 0 {
        let mut buckets: Vec = vec![Vec::new(); 10];
        for &num in &arr {
            let digit = (num / exp) % 10;
            buckets[digit as usize].push(num);
        }
        arr.clear();
        for bucket in buckets {
            for num in bucket {
                arr.push(num);
            }
        }
        exp *= 10;
    }
    arr
}

let input = vec![329, 457, 657, 839, 436, 720, 355];
let sorted = radix_sort(input);
println!("{:?}", sorted);

hard

A. [329, 436, 355, 457, 657, 720, 839]

B. [839, 720, 657, 457, 436, 355, 329]

C. [329, 355, 436, 457, 657, 720, 839]

D. [355, 329, 436, 457, 657, 720, 839]

Solution

1. Step 1: Understand the radix sort passes

   The function sorts by digits starting from least significant (units), then tens, then hundreds until max digit processed.

2. Step 2: Trace sorting steps on input

   After all passes, the vector is sorted ascending: [329, 355, 436, 457, 657, 720, 839].

3. Final Answer:

   [329, 355, 436, 457, 657, 720, 839] -> Option C

4. Quick Check:

   Radix sort final output = sorted ascending [OK]

Hint: Radix sort outputs fully sorted list ascending [OK]

Common Mistakes:

• Confusing order as descending
• Missing clearing array before collecting buckets
• Not multiplying exp by 10 each iteration