Merge Sort

Merge sort is a classic divide-and-conquer sorting algorithm. It works by splitting the list into smaller halves, sorting each half recursively, and then merging the sorted halves back together. Because it relies on merging rather than swapping or shifting, merge sort provides stable, predictable performance and is one of the most widely used sorting techniques in practice.

Example Walk-through

Consider this array:

[38, 27, 43, 3, 9, 82, 10]

Merge sort divides the array into halves until each piece has only one element.

Step 1 - Divide

[38, 27, 43, 3, 9, 82, 10]
          /          \
 [38, 27, 43, 3]    [9, 82, 10]

Split again:

[38, 27, 43, 3]       [9, 82, 10]
    /     \               /    \
[38, 27] [43, 3]       [9]   [82, 10]

Split again:

[38] [27]  [43] [3]   [9]  [82] [10]

Now all pieces have one element - they are trivially sorted.

Step 2 - Conquer and Merge

Now we merge upward, always combining two sorted lists into one sorted list.

Merge [38] and [27] → [27, 38] Merge [43] and [3] → [3, 43]

Next level:

Merge [27, 38] and [3, 43] → [3, 27, 38, 43]

On the right side:

Merge [82] and [10] → [10, 82]

Then:

Merge [9] and [10, 82] → [9, 10, 82]

Final merge:

Merge [3, 27, 38, 43] and [9, 10, 82] → [3, 9, 10, 27, 38, 43, 82]

Merge sort’s strength is the efficiency and predictability of its divide-and-conquer strategy.

Rust Implementation

Merge sort requires temporary storage during merging. This implementation uses a recursive divide-and-conquer approach with a helper merge function.

pub fn merge_sort(arr: &mut [i32]) {
    let n = arr.len();
    if n <= 1 {
        return;
    }

    let mid = n / 2;
    merge_sort(&mut arr[..mid]);
    merge_sort(&mut arr[mid..]);

    // Merge the two sorted halves
    let mut temp = arr.to_vec();
    merge(&arr[..mid], &arr[mid..], &mut temp[..]);
    arr.copy_from_slice(&temp);
}

fn merge(left: &[i32], right: &[i32], out: &mut [i32]) {
    let mut i = 0;
    let mut j = 0;
    let mut k = 0;

    while i < left.len() && j < right.len() {
        if left[i] <= right[j] {
            out[k] = left[i];
            i += 1;
        } else {
            out[k] = right[j];
            j += 1;
        }
        k += 1;
    }

    // Copy any remaining elements
    while i < left.len() {
        out[k] = left[i];
        i += 1;
        k += 1;
    }

    while j < right.len() {
        out[k] = right[j];
        j += 1;
        k += 1;
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn it_sorts() {
        let mut input = vec![38, 27, 43, 3, 9, 82, 10];
        merge_sort(&mut input);
        assert_eq!(input, vec![3, 9, 10, 27, 38, 43, 82]);
    }
}

Example Usage

fn main() {
    let mut values = vec![5, 2, 4, 7, 1, 3, 2, 6];
    merge_sort(&mut values);
    println!("{:?}", values); // [1, 2, 2, 3, 4, 5, 6, 7]
}

Time and Space Complexity

Merge sort has one of the most predictable performance profiles of all sorting algorithms.

Space Complexity

Unlike bubble, selection, and insertion sort, merge sort is not an in-place algorithm - the merging phase needs additional storage.

Playground Links

Rust - Merge Sort