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
#![feature(test)]
#![feature(const_fn)]
extern crate test;
extern crate rand;
extern crate num;
pub mod tests;
use num::pow;
pub trait Indexed {
fn get_index(&self) -> u64;
}
pub fn sort<T: Clone + Default + Indexed> (source:&Vec<T>) -> Vec<T> {
let radix = 8;
let steps = (64 / radix) as usize;
let buckets:usize = pow(2, radix);
let mask:u64 = (buckets - 1) as u64;
let mut shift:usize = 0;
let mut bucket_sums = vec![0usize; buckets];
let mut bucket_counts = vec![0usize; buckets];
let count = source.len();
let mut buffers = [Some(source.clone()), Some(vec![Default::default(); count])];
for step in 0..steps {
let (source, workspace) = {
let mut iter = buffers.iter_mut();
let b0 = iter.next().unwrap();
let b1 = iter.next().unwrap();
if step % 2 == 0 {
(b0.as_ref().unwrap(), b1.as_mut().unwrap())
} else {
(b1.as_ref().unwrap(), b0.as_mut().unwrap())
}
};
if step > 0 {
for bucket in &mut bucket_counts {
*bucket = 0;
}
}
for entry in source.iter() {
let code = entry.get_index();
let idx = (code >> shift & mask) as usize;
bucket_counts[idx] += 1;
}
bucket_sums[0] = 0;
for i in 1..buckets {
bucket_sums[i] = bucket_sums[i - 1] + bucket_counts[i - 1];
}
for entry in source.iter() {
let entry = entry.clone();
let code = entry.get_index();
let idx = (code >> shift & mask) as usize;
let sum = bucket_sums[idx];
workspace[sum] = entry;
bucket_sums[idx] = sum + 1;
}
shift = shift + radix;
}
buffers[steps % 2].take().unwrap()
}