competitive_programming_lib/Sorting/
merge_sort.rs

1pub fn merge_sort(arr: &mut [i32]) {
2    let len = arr.len();
3    if len <= 1 {
4        return;
5    }
6
7    let mid = len / 2;
8    merge_sort(&mut arr[..mid]);
9    merge_sort(&mut arr[mid..]);
10    merge(arr, mid);
11}
12
13fn merge(arr: &mut [i32], mid: usize) {
14    let mut left = arr[..mid].to_vec();
15    let mut right = arr[mid..].to_vec();
16
17    let (mut i, mut j, mut k) = (0, 0, 0);
18    while i < left.len() && j < right.len() {
19        if left[i] <= right[j] {
20            arr[k] = left[i];
21            i += 1;
22        } else {
23            arr[k] = right[j];
24            j += 1;
25        }
26        k += 1;
27    }
28
29    while i < left.len() {
30        arr[k] = left[i];
31        i += 1;
32        k += 1;
33    }
34
35    while j < right.len() {
36        arr[k] = right[j];
37        j += 1;
38        k += 1;
39    }
40}