# 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
`w`

th 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`

.

- Create a

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;
as usize] += 1;
counter[e }
let mut acc = 0;
for e in counter.iter_mut() {
let p = *e;
*e = acc;
+= p;
acc }
for &e in array.iter() {
let i = (e >> (s * 8)) & 0xff;
as usize]] = e;
out[counter[i as usize] += 1;
counter[i }
= out;
array println!("{:?}", array);
}
}
```