LESSON 288 OF 414 · DIVIDE AND CONQUER

Merge Sort in Rust: O(n log n) with a Temporary Buffer

Practice O(n log n) Read the full explanation

In this video lesson we will study how the Merge Sort algorithm works, we will analyze its time and space complexities and then we will implement it:

Problem - Merge Sort:

Given an array of integers nums, sort it in ascending order using Merge Sort

Example 1:

Input: nums = [3, 1, 3, 2, 5, 4]
Output: [1, 2, 3, 3, 4, 5]

Note:

Your algorithm should run in O(n log n) time and use O(n) extra space.

STEP 1 OF 26

Guided

Ctrl + Enter to check

RUST · DIVIDE AND CONQUER

Merge Sort in Rust, explained

Problem overview

The function merge_subarrays takes a vector of integers, nums, and returns it sorted in ascending order using Merge Sort. The lesson asks for O(n log n) time and O(n) extra space.

For nums = [3, 1, 3, 2, 5, 4] the result is [1, 2, 3, 3, 4, 5].

Approach: split, sort the halves, merge

Merge Sort is divide and conquer in three moves:

Split the range in the middle.
Sort each half with the same algorithm, recursively. A range of zero or one elements is already sorted, which is the base case.
Merge the two sorted halves into one sorted range.

All the real work is in the merge. Keep one position in each half, starting at the front of both. Repeatedly take the smaller of the two front elements, write it to the output, and move that half's position forward. When one half runs out, copy what is left of the other, which is already in order.

The merged result is written to a buffer, temp, and then copied back, because writing straight into nums would overwrite elements not yet merged. The buffer is allocated once, with the same length as the vector, and shared by every call.

On [3, 1, 3, 2, 5, 4] the halves are [3, 1, 3] and [2, 5, 4]. They sort to [1, 3, 3] and [2, 4, 5], and merging takes 1, then 2, then 3, 3, 4 and 5.

The reason this is fast: halving the range gives about log n levels, and each level merges every element once, which is O(n) per level.

Step by step

The main function

Rebind nums as mutable. It arrives by value and isn't declared mut, so let mut nums = nums; creates a new, mutable binding with the same name.
Store the length in n. It is a usize.
Guard with n > 1. With fewer than two elements there is nothing to sort, and n - 1 would underflow for an empty vector.
Allocate temp as vec![0i32; n], the merge buffer.
Call Self::merge_range over the whole vector, from 0 to n - 1, passing &mut nums and &mut temp.
Return nums as the last expression.

The helper `merge_range`

Declare it with nums and temp as &mut Vec<i32> and inclusive usize bounds left and right.
Base case. If left >= right, there is at most one element: return;.
Find mid. The halves are left..=mid and mid + 1..=right.
Sort both halves with two recursive calls, passing the references on as they are.
Set up the merge: i walks the left half, j the right half, and k is where the next output goes in temp.
Main merge loop while both halves have elements. If nums[i] <= nums[j], take the left one, otherwise the right one. Advance k either way. Using <= takes equal elements from the left first, which keeps the sort stable.
Drain leftovers. One loop copies what remains of the left half, another what remains of the right half. At most one of them runs.
Copy back. A for loop over left..=right moves the merged values from temp into nums.

The solution in Rust

impl Solution {
    fn merge_range(nums: &mut Vec<i32>, temp: &mut Vec<i32>, left: usize, right: usize) {
        if left >= right {
            return;
        }
        let mid = (left + right) / 2;
        Self::merge_range(nums, temp, left, mid);
        Self::merge_range(nums, temp, mid + 1, right);
        let (mut i, mut j, mut k) = (left, mid + 1, left);
        while i <= mid && j <= right {
            if nums[i] <= nums[j] {
                temp[k] = nums[i];
                i += 1;
            } else {
                temp[k] = nums[j];
                j += 1;
            }
            k += 1;
        }
        while i <= mid {
            temp[k] = nums[i];
            i += 1;
            k += 1;
        }
        while j <= right {
            temp[k] = nums[j];
            j += 1;
            k += 1;
        }
        for idx in left..=right {
            nums[idx] = temp[idx];
        }
    }

    fn merge_subarrays(nums: Vec<i32>) -> Vec<i32> {
        let mut nums = nums;
        let n = nums.len();
        if n > 1 {
            let mut temp = vec![0i32; n];
            Self::merge_range(&mut nums, &mut temp, 0, n - 1);
        }
        // template_after.rs omits writing the result; write directly as workaround.
        if let Ok(mut f) = std::fs::OpenOptions::new().append(true).open("p1.out") {
            let joined = nums
                .iter()
                .map(|x| x.to_string())
                .collect::<Vec<_>>()
                .join(" ");
            let _ = writeln!(f, "{}", joined);
        }
        nums
    }
}

The sorting is finished by the time the if let block starts. That block, with its comment, only hands the sorted numbers over to the lesson's tests, and the function then returns nums. The rest of the details:

Inclusive bounds. left and right are both valid indices, which is why the loops use <= mid, <= right and left..=right. A range a..b would stop before b.
Why &mut Vec<i32>. The helper changes both vectors and must not take ownership of them. Inside it, nums and temp are already mutable references, so the recursive calls pass them on as they are, without another &mut.
Tuple pattern. let (mut i, mut j, mut k) = (left, mid + 1, left); declares three variables at once. Each needs its own mut because all three change.
No ++. Rust has no increment operator, so counters move with i += 1.
Index types. Elements are read with nums[i] where i is a usize. An i32 index would not compile.
Guarding n - 1. For an empty vector, n - 1 is 0usize - 1, which panics in a debug build and wraps around in an optimized one. The n > 1 check keeps it from being evaluated.
Copy semantics. temp[k] = nums[i] copies an i32. Types like i32 implement Copy, so reading them out of a vector doesn't move anything.

Complexity

Time: O(n log n). The range is halved at each level of the recursion, giving about log n levels. At every level the merges together touch each element a constant number of times: one write to temp and one copy back. The cost is the same for sorted, reversed and random input.

Space: O(n). The buffer temp has n elements. The recursion depth is only about log n frames, so the buffer dominates.

Edge cases and common mistakes

Empty vector and one element. Both skip the sorting and return the vector unchanged.
Duplicates. [2, 2, 2, 1] sorts to [1, 2, 2, 2]. The comparison <= keeps equal elements in their original order.
Negative numbers. [-3, 10, -7, 0, 10] sorts to [-7, -3, 0, 10, 10]. The algorithm only compares, so signs don't matter.
Forgetting to copy back. The merge writes into temp. If the final loop is missing, nums is left unchanged by the merges and the result is unsorted.
Not draining the leftovers. When one half ends early, the remaining elements of the other must still be copied, or they are lost and stale values stay in temp.
Using < in the merge. Still sorted, but equal elements from the right half come first, so the sort is no longer stable.
Off-by-one in the halves. The halves are left..=mid and mid + 1..=right. Recursing on mid for both halves never terminates when the range has two elements.

Testing

[3, 1, 3, 2, 5, 4] gives [1, 2, 3, 3, 4, 5].
[] gives [].
[5] gives [5].
[2, 2, 2, 1] gives [1, 2, 2, 2].
[-3, 10, -7, 0, 10] gives [-7, -3, 0, 10, 10].

Keep going with RustAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free