DEV Community

loading...

Implementing Merge Sort in Rust

felixfaisal
Linux Foundation Mentee @FD.io | MLH Fellow'21 | FOSSEE Fellow'20 | Open Source Contributor
・2 min read

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
Enter fullscreen mode Exit fullscreen mode

Let's visualize this psuedocode using a diagram
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
}
Enter fullscreen mode Exit fullscreen mode

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
}
Enter fullscreen mode Exit fullscreen mode

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);
}
Enter fullscreen mode Exit fullscreen mode

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]
Enter fullscreen mode Exit fullscreen mode

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

Discussion (2)

Collapse
rsalmei profile image
Rogério Sampaio de Almeida

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

Collapse
felixfaisal profile image
felixfaisal Author

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.