Implementing Merge Sort in Rust

Merge sort is arguably the most popular divide and conquer algorithm, It is one of the first algorithms any software engineer learns while learning algorithms and also while preparing for interviews. Let's implement merge sort in Rust

Divide and Conquer

Divide and Conquer is an algorithm design paradigm where we break down the problem statement into two or more parts until it can be solved directly.

Here we want to sort an array(or vector) in asceding order so we first break down the problem using recursion and then solve the problem.

Merge Sort Algorithm

Here's the psuedocode for merge sort algorithm

Step 1: Divide the array into two parts 
Step 2: Sort one half of the array 
Step 3: Sort second half of the array 
Step 4: Merge the two halfs
Step 5: Perform these operations recursively

Let's visualize this psuedocode using a diagram

Rust code

fn merge_sort(mut arr: Vec<i32>, left: usize, right: usize) -> Vec<i32> {
    if right - 1 > left {
        let mid = left + (right - left) / 2;
        arr = merge_sort(arr, left, mid);
        arr = merge_sort(arr, mid, right);
        arr = merge(arr, left, mid, right);
    }
    arr
}

Here right - 1 > left is the terminating condition meaning that the array cannot be divided anymore. We calculate the midpoint of the array and then divide them further recursively after which we merge the arrays by calling merge(arr, left, mid, right).

fn merge(mut arr: Vec<i32>, left: usize, mid: usize, right: usize) -> Vec<i32> {
    let n1 = mid - left;
    let n2 = right - mid;
    let mut L1 = arr.clone();
    let mut R1 = arr.clone();
    let L = &L1[left..mid];
    let R = &R1[mid..right];
    /* Merge the temp arrays back into arr[l..r]*/
    let mut i = 0; // Initial index of first subarray
    let mut j = 0; // Initial index of second subarray
    let mut k = left; // Initial index of merged subarray
    while i < n1 && j < n2 {
        if L[i] < R[j] {
            arr[k] = L[i];
            i = i + 1;
        } else {
            arr[k] = R[j];
            j = j + 1;
        }
        k = k + 1;
    }
    while i < n1 {
        arr[k] = L[i];
        i = i + 1;
        k = k + 1;
    }
    /* Copy the remaining elements of R[], if there
    are any */
    while j < n2 {
        arr[k] = R[j];
        j = j + 1;
        k = k + 1;
    }
    arr
}

Here we merge the two sorted sub arrays in ascending order into a single array, We do this by checking less than condition and then inserting into the array.

Output

Let's run these functions using a main function

fn main() {
    let mut arr: Vec<i32> = vec![64, 34, 25, 8, 22, 11, 9];
    arr = merge_sort(arr.clone(), 0, arr.len());
    println!("Sorted array is {:?}", arr);
}

Here's the output!

Finished dev [unoptimized + debuginfo] target(s) in 2.83s
     Running `target/debug/rust-code-gen`
Sorted array is [8, 9, 11, 22, 25, 34, 64]

There are definitely better ways of implementing this algorithm. Implementing fundamental algorithms in Rust can help beginners understand Rust better and feel more confident.