Radix sort

Radix sort is an algorithm that sorts integers in O(nw) time, where w denotes the storage size of the integers.

Briefly, it works like this:

• Pick a radix (e.g. 256, because that fits nicely in a byte).
• Do the following w times, where w is the maximum amount of radices in a number):
  • Create a counter array of size 256
  • Create an output array of size n, where n is the size of the input
  • For each element, take the wth radix, use that as an index in the counter array and increase the counter by 1.
  • Create an accumulator, iterate over all values in counter
    • Overwrite them with the accumulator value
    • Increase the accumulator value by the previous counter value
  • Our counter array is now actually an offset array. We can now iterate over all elements again and directly put them in the right spot.
  • Swap (or overwrite) the input with the output.

Note that an implementation can start with either the LSB or the MSB.

Implementations

Rust

fn main() {
    let mut array: [u32; 10] = [523442, 2, 9, 49034394, 3, 42, 22, 13, 43043, 202032232];
    let mut out = [0; 10];

    println!("{:?}", array);
    for s in 0..4 {
        let mut counter = [0; 256];

        for &e in array.iter() {
            let e = (e >> (s * 8)) & 0xff;
            counter[e as usize] += 1;
        }

        let mut acc = 0;
        for e in counter.iter_mut() {
            let p = *e;
            *e = acc;
            acc += p;
        }

        for &e in array.iter() {
            let i = (e >> (s * 8)) & 0xff;
            out[counter[i as usize]] = e;
            counter[i as usize] += 1;
        }

        array = out;
        println!("{:?}", array);
    }
}