Implementing Merge Sort in Rust
Tags: rust, algorithms, interview, sorting
Published: 2021-07-23 13:57:49

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
![Diagram](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/n5km9h1x4d928g9laghx.png)

## Rust code 
```rust 
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)`. 
```rust
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 
```rust 
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!
```bash 
    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.