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

/// Efficient sorting against large sets. Requires `O(n)` aux. space.
///
/// This divide-and-conquer sorting algorithm, while inefficient with memory use, performs
/// `O(n log n)` in average, worst and best case scenarios even against large sets of data.
pub fn merge_sort<A: Ord + Clone>(data: &[A]) -> Vec<A> {
    fn divide<A: Ord + Clone>(data: &[A]) -> Vec<A> {
        match data.len() {
            0 => vec![],
            1 => vec![data[0].clone()],
            size => {
                let middle = size / 2;
                conquer(divide(data.slice_to(middle)), divide(data.slice_from(middle)))
            }
        }
    }

    fn conquer<A: Ord + Clone>(left: Vec<A>, right: Vec<A>) -> Vec<A> {
        let mut left_index = 0;
        let mut right_index = 0;

        let left_size = left.len();
        let right_size = right.len();

        let mut result = Vec::with_capacity(left_size + right_size);

        while left_index < left_size && right_index < right_size {
            if left[left_index] < right[right_index] {
                result.push(left[left_index].clone());
                left_index += 1;
            } else {
                result.push(right[right_index].clone());
                right_index += 1;
            }
        }

        result.push_all(left.slice_from(left_index));
        result.push_all(right.slice_from(right_index));

        result
    }

    divide(data)
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_merge_sort() {
        let mut data = vec![9, 8, 1, 5, 3, 16, 2, 0, 4];
        data = merge_sort(data.as_mut_slice());
        assert_eq!([0, 1, 2, 3, 4, 5, 8, 9, 16], data.as_slice());
    }
}