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.
Top comments (2)
Man, your
mergehas very poor performance, because you are cloning the whole array twice inside a recursive function! Everymergecall, 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.Also, it is written like in C, it could be very improved using Rust constructs, like iterators, slices, and some trait magic.
Here it is one that's very good: dev.to/creativcoder/merge-k-sorted...
I specially like the one in the comments.
Hey, Thanks a lot for sharing the article, I'm still exploring Rust plus learning other things. I'm familiar with C so I was sort of seeing how it would be implemented in Rust Syntax.