Intro

In this article, I've explained how mergesort works and also provided an implementation in rust language.

Mergesort Algorithm

Mergesort it's another divide-and-conquer algorithm similar to quicksort. The algorithm consists of two steps:

Divide the array to be merged into halves till the resulting array it's of size one.
The second step is to apply bottom up merging procedure which works as follow:
- we compare the first element from each array to be merged; the smallest will be included in a new merged array, and removed from the partitioned array.
- we repeat the procedure till there are no more elements in any of the arrays to be merged.

Analysis

Time complexity of mergesort is O(nlogn) in all cases. Space complexity is O(n) we will need an extra array to store the merged parts from left and right.

Implementation in rust

pub fn mergesort<T: PartialOrd + Copy>(arr: &mut [T]) {
    _mergesort(arr, 0, arr.len() - 1);
}

fn _mergesort<T: PartialOrd + Copy>(arr: &mut [T], left: usize, right: usize) {
    if left < right {
        let mid = (left + right) / 2;
        _mergesort(arr, left, mid);
        _mergesort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

fn merge<T: PartialOrd + Copy>(arr: &mut [T], left: usize, mid: usize, right: usize) {
    let left_arr = &arr[left..=mid].to_owned();
    let right_arr = &arr[mid + 1..=right].to_owned();

    let mut i = 0;
    let mut j = 0;

    for k in left..=right {
        if i < left_arr.len() && j < right_arr.len() {
            if left_arr[i] < right_arr[j] {
                arr[k] = left_arr[i];
                i += 1;
            } else {
                arr[k] = right_arr[j];
                j += 1;
            }
        } else if i >= left_arr.len() {
            arr[k] = right_arr[j];
            j += 1;
        } else {
            arr[k] = left_arr[i];
            i += 1;
        }
    }
}

Let's be in contact and join my newsletter.

Join 0 other subscribers.

Blog posts

Mergesort implemented in rust language