sorting_algorithm/
merge_sort.rs

1/// Sorts a data set using Merge Sort
2///
3/// Average time complexity: O(n logn)
4///
5/// # Example
6///
7/// ```
8/// use sorting_algorithm::merge_sort;
9///
10/// fn main() {
11///     let mut data = [3, 1, 2, 5, 4];
12///     
13///     merge_sort::sort(&mut data);
14///
15///     assert_eq!(data, [1, 2, 3, 4, 5]);
16/// }
17/// ```
18pub fn sort<T: Ord + Clone>(data: &mut [T]) {
19    if data.len() > 1 {
20        let mid = data.len() / 2;
21
22        sort(&mut data[..mid]);
23        sort(&mut data[mid..]);
24
25        merge(data, mid);
26    }
27}
28
29fn merge<T: Ord + Clone>(data: &mut [T], mid: usize) {
30    let left = data[..mid].to_vec();
31    let right = &data[mid..].to_vec();
32
33    let mut i = 0;
34    let mut j = 0;
35    let mut k = 0;
36
37    while i < left.len() && j < right.len() {
38        if left[i] < right[j] {
39            data[k] = left[i].clone();
40            i += 1
41        } else {
42            data[k] = right[j].clone();
43            j += 1
44        }
45
46        k += 1;
47    }
48
49    while i < left.len() {
50        data[k] = left[i].clone();
51        i += 1;
52        k += 1;
53    }
54
55    while j < right.len() {
56        data[k] = right[j].clone();
57        j += 1;
58        k += 1;
59    }
60}
sorting_algorithm/merge_sort.rs

sorting_algorithm/
merge_sort.rs
