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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

use super::super::{RadixKey, Radixable};
use super::utils::Params;

fn counting_sort_aux<T, K>(arr: &mut [T], p: Params)
where
    T: Radixable<K> + Copy + PartialOrd,
    K: RadixKey,
{
    let dummy = arr[0];
    let mut histogram = vec![0; p.radix_range];
    let mask = dummy.default_mask(p.radix);

    let quotient = arr.len() / 4;
    let remainder = arr.len() % 4;
    for q in 0..quotient {
        unsafe {
            let i = q * 4;
            let bucket0 = arr.get_unchecked(i).extract(mask, 0);
            let bucket1 = arr.get_unchecked(i + 1).extract(mask, 0);
            let bucket2 = arr.get_unchecked(i + 2).extract(mask, 0);
            let bucket3 = arr.get_unchecked(i + 3).extract(mask, 0);
            histogram[bucket0] += 1;
            histogram[bucket1] += 1;
            histogram[bucket2] += 1;
            histogram[bucket3] += 1;
        }
    }
    let offset = quotient * 4;
    for i in 0..remainder {
        unsafe {
            let bucket = arr.get_unchecked(offset + i).extract(mask, 0);
            histogram[bucket] += 1;
        }
    }

    let dummy = arr[0];

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

/// # Counting sort
///
/// An implementation of the
/// [Counting sort](https://en.wikipedia.org/wiki/Counting_sort)
/// algorithm.
///
/// Counting sort is very fast for inputs with a small bit representation.
///
/// This Counting sort has been a bit customized since it takes a radix input.
pub fn counting_sort<T, K>(arr: &mut [T], radix: usize)
where
    T: Radixable<K> + Copy + PartialOrd,
    K: RadixKey,
{
    if arr.len() < 2 {
        return;
    }

    let offset = 0;
    let level = 0;
    let max_level = 1;
    let params = Params::new(level, radix, offset, max_level);

    counting_sort_aux(arr, params);
}