sorts/
merge_sort.rs

1/// Sorts a slice using
2/// [merge sort](https://en.wikipedia.org/wiki/Merge_sort).
3///
4/// # Examples
5/// ```
6/// let mut slice = vec![3,2,1,4];
7/// sorts::merge_sort(&mut slice);
8/// assert_eq!(slice, &[1,2,3,4]);
9/// ```
10pub fn merge_sort<T: PartialOrd + Copy>(s: &mut [T]) {
11    let len = s.len();
12    if len < 2 {
13        return;
14    }
15
16    let mid = len / 2;
17    merge_sort(&mut s[..mid]);
18    merge_sort(&mut s[mid..]);
19
20    let mut tmp = Vec::with_capacity(len);
21    let mut i = 0;
22    let mut j = mid;
23
24    while i < mid && j < len {
25        if s[i] < s[j] {
26            tmp.push(s[i]);
27            i += 1;
28        } else {
29            tmp.push(s[j]);
30            j += 1;
31        }
32    }
33    if i < mid {
34        tmp.extend_from_slice(&s[i..mid]);
35    } else if j < len {
36        tmp.extend_from_slice(&s[j..len]);
37    }
38
39    s.copy_from_slice(&tmp[..]);
40}