sorting_algorithm/
merge_sort.rs

1/// Sorts a data set using Merge Sort
2///
3/// Average time complexity: O(n logn)
4///
5/// # Examples
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
36    for element in data {
37        if i < left.len() && j < right.len() {
38            if left[i] < right[j] {
39                *element = left[i].clone();
40                i += 1;
41            } else {
42                *element = right[j].clone();
43                j += 1;
44            }
45        } else if i < left.len() {
46            *element = left[i].clone();
47            i += 1;
48        } else if j < right.len() {
49            *element = right[j].clone();
50            j += 1;
51        }
52    }
53}
sorting_algorithm/merge_sort.rs

sorting_algorithm/
merge_sort.rs
