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;
}
}
});
}
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);
}