competitive_programming_lib/Sorting/
radix_sort.rs

1pub fn radix_sort(arr: &mut [i32]) {
2    let max = *arr.iter().max().unwrap_or(&0);
3    let mut exp = 1;
4    while max / exp > 0 {
5        counting_sort(arr, exp);
6        exp *= 10;
7    }
8}
9
10fn counting_sort(arr: &mut [i32], exp: i32) {
11    let mut output = vec![0; arr.len()];
12    let mut count = vec![0; 10];
13
14    for &num in arr.iter() {
15        let index = (num / exp % 10) as usize;
16        count[index] += 1;
17    }
18
19    for i in 1..10 {
20        count[i] += count[i - 1];
21    }
22
23    for &num in arr.iter().rev() {
24        let index = (num / exp % 10) as usize;
25        output[count[index] as usize - 1] = num;
26        count[index] -= 1;
27    }
28
29    arr.copy_from_slice(&output);
30}