rust_sort/
merge_sort.rs

1use super::Sortable;
2
3/// Merge sorts stable, not in-place, in ascending order a mutable ref slice of type T: Sortable
4///
5/// Merge sort is an efficient divide and conquer sort.
6/// Conceptually, a merge sort works as follows:
7
8/// Divide the unsorted list into n sublists, each containing 1 element (a list of 1 element is considered sorted).
9/// Repeatedly merge sublists to produce new sorted sublists until there is only 1 sublist remaining.
10/// This will be the sorted list.
11///
12/// # Examples
13///
14/// ```
15/// use rust_sort::merge_sort::sort;
16///
17/// let mut arr = [3, 2, 1, 7, 9, 4, 1, 2];
18/// sort(&mut arr);
19/// assert_eq!(arr, [1, 1, 2, 2, 3, 4, 7, 9]);
20///
21/// ```
22pub fn sort<T: Sortable>(list: &mut [T]) {
23    // merge_sort produces a new list so iterating and mutating existing list here.
24    let merged = merge_sort(list);
25    let mut merged_iter = merged.iter();
26    for v in list.iter_mut() {
27        *v = *merged_iter.next()
28            .expect("merge list length does not match input list length, should never happen");
29    }
30}
31
32fn merge_sort<T: Sortable>(list: &mut [T]) -> Vec<T> {
33    let len = list.len();
34    if len <= 1 {
35        return list.to_vec();
36    }
37    let mid = len /2;
38    let mut left =  merge_sort(&mut list[..mid]);
39    let mut right = merge_sort(&mut list[mid..]);
40
41    merge(&mut left, &mut right)
42}
43
44fn merge<T:Sortable>(left: &mut [T], right: &mut [T]) -> Vec<T> {
45    let mut list = Vec::with_capacity(left.len() + right.len());
46    let mut left_iter = left.iter().peekable();
47    let mut right_iter = right.iter().peekable();
48    loop {
49        match (left_iter.peek(), right_iter.peek()) {
50            (None, None) => break,
51            (Some(&&l), None) => {
52                list.push(l);
53                left_iter.next();
54            },
55            (None, Some(&&r)) => {
56                list.push(r);
57                right_iter.next();
58            },
59            (Some(&&l), Some(&&r)) => {
60                if l < r {
61                    list.push(l);
62                    left_iter.next();
63                } else {
64                    list.push(r);
65                    right_iter.next();
66                }
67            },
68        }
69    }
70    list
71}
rust_sort/merge_sort.rs

rust_sort/
merge_sort.rs
