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
pub fn merge_sort<T: PartialOrd>(mut input: Vec<T>) -> Vec<T> {
if input.len() <= 1 {
return input;
}
let mut result = Vec::with_capacity(input.len());
let r_merged = merge_sort(input.split_off(input.len() / 2));
let l_merged = merge_sort(input);
let mut l_rest = l_merged.into_iter();
let mut r_rest = r_merged.into_iter();
let mut l_next = l_rest.next();
let mut r_next = r_rest.next();
loop {
match l_next {
Some(ref l_val) => {
match r_next {
Some(ref r_val) => {
if r_val < l_val {
result.push(r_next.take().unwrap());
r_next = r_rest.next();
} else {
result.push(l_next.take().unwrap());
l_next = l_rest.next();
}
},
None => {
result.push(l_next.take().unwrap());
result.extend(l_rest);
return result
}
}
},
None => {
if let Some(r_val) = r_next {
result.push(r_val);
}
result.extend(r_rest);
return result
}
}
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_merge_sort() {
let tester = vec![1, 0, 9, 3, 12, 2];
assert_eq!(merge_sort(tester), vec![0, 1, 2, 3, 9, 12])
}
}