Merge Sort Algorithm in Rust

1. Introduction

Merge Sort is a divide-and-conquer sorting algorithm that divides the array into two halves, recursively sorts them, and then merges the two sorted halves. It's known for its consistent O(n log n) performance, making it more predictable in terms of performance than algorithms like QuickSort, which has a worst-case scenario of O(n^2).

2. Implementation Steps

1. If the array has only one element or none, it's already sorted.

2. Split the array into two halves.

3. Recursively sort both halves.

4. Merge the two halves together.

5. Return the merged and sorted array.

3. Implementation in Rust Programming

fn merge<T: Ord>(left: &[T], right: &[T], arr: &mut [T]) {
    let mut i = 0;
    let mut j = 0;
    let mut k = 0;
    while i < left.len() && j < right.len() {
        if left[i] <= right[j] {
            arr[k] = left[i].clone();
            i += 1;
        } else {
            arr[k] = right[j].clone();
            j += 1;
        }
        k += 1;
    }
    while i < left.len() {
        arr[k] = left[i].clone();
        i += 1;
        k += 1;
    }
    while j < right.len() {
        arr[k] = right[j].clone();
        j += 1;
        k += 1;
    }
}
fn merge_sort<T: Ord + Clone>(arr: &mut [T]) {
    let mid = arr.len() / 2;
    if mid == 0 {
        return;
    }
    let (left, right) = arr.split_at_mut(mid);
    let left = left.to_vec();
    let right = right.to_vec();
    merge_sort(&mut left.clone());
    merge_sort(&mut right.clone());
    merge(&left, &right, arr);
}
fn main() {
    let mut numbers = [38, 27, 43, 3, 9, 82, 10];
    merge_sort(&mut numbers);
    println!("{:?}", numbers);  // Prints: [3, 9, 10, 27, 38, 43, 82]
}

Output:

[3, 9, 10, 27, 38, 43, 82]

Explanation:

1. We define a helper function merge which combines two sorted slices into one.

2. In the merge function, three pointers i, j, and k track the position in the left slice, right slice, and merged array respectively.

3. The function picks the smaller element from the left or right slice and places it in the array, incrementing the corresponding pointer.

4. After finishing one of the slices, it copies over any remaining elements from the other slice.

5. merge_sort is the main function that implements the divide and conquer strategy.

6. The array is divided into two halves until we get arrays of length 1.

7. These smaller arrays (halves) are then sorted and merged back together.

8. In the main function, an example array is sorted and then printed.