felixfaisal

Posted on

# 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.

Man, your `merge` has very poor performance, because you are cloning the whole array twice inside a recursive function! Every `merge` call, even the ones with only one element on each side, will clone the whole array twice... You could try to make it in-place, just swapping elements.