voracious_radix_sort 1.2.0

State of the art radix sort algorithms. Single thread and multi thread versions.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

const UNROLL_SIZE: usize = 4;

pub fn cs_u16(arr: &mut [u16]) {
    let size = arr.len();
    if size < 2 {
        return;
    }

    let mut histogram = vec![0; 65536];

    let remainder = size % UNROLL_SIZE;
    let (arr_main, arr_remainder) = arr.split_at_mut(size - remainder);

    arr_main.chunks_exact(UNROLL_SIZE).for_each(|chunk| {
        histogram[chunk[0] as usize] += 1;
        histogram[chunk[1] as usize] += 1;
        histogram[chunk[2] as usize] += 1;
        histogram[chunk[3] as usize] += 1;
    });
    arr_remainder.iter().for_each(|item| {
        histogram[*item as usize] += 1;
    });

    let mut position = 0;
    histogram.iter().enumerate().for_each(|(value, count)| {
        if *count > 0 {
            let v = value as u16;
            let quotient = *count / 4;
            let remainder = count % 4;
            for _ in 0..quotient {
                unsafe {
                    *arr.get_unchecked_mut(position) = v;
                    *arr.get_unchecked_mut(position + 1) = v;
                    *arr.get_unchecked_mut(position + 2) = v;
                    *arr.get_unchecked_mut(position + 3) = v;
                    position += 4;
                }
            }
            for _ in 0..remainder {
                unsafe {
                    *arr.get_unchecked_mut(position) = v;
                    position += 1;
                }
            }
        }
    });
}