LESSON 257 OF 414 · TWO POINTERS

Merge Two Sorted Arrays in Rust: O(n + m) with Two Pointers

Practice O(n + m) Read the full explanation

Given two sorted arrays of integers, merge them into one sorted array containing all numbers

Example:

Input: first =[1, 4, 8],
       second = [1, 3, 4, 17]

Output: [1, 1, 3, 4, 4, 8, 17]

Note:

Your algorithm should run in O(n + m) time and use O(n + m) extra space, where n and m are the lengths of the two arrays.

STEP 1 OF 10

Guided

Ctrl + Enter to check

Merge Sorted Arrays in Rust, explained

Problem overview

The function merge receives two vectors of integers, first and second, each already sorted in ascending order. It must return one sorted vector with all the numbers from both, duplicates included. For first = [1, 4, 8] and second = [1, 3, 4, 17] the answer is [1, 1, 3, 4, 4, 8, 17].

The statement asks for O(n + m) time and O(n + m) extra space, where n and m are the two lengths. The extra space is the output vector.

Approach: always take the smaller front element

One simple way is to append both vectors and sort the result. That costs O((n + m) log(n + m)) and ignores the fact that the inputs are sorted. The linear approach uses that fact.

In a sorted vector, the smallest element not yet used is always the first unused one. So the smallest element not yet merged is one of two candidates: the first unused element of first, or the first unused element of second. Compare them, move the smaller into the output, and advance the index of the vector it came from. Repeat until one vector is used up. The other may still have elements, and since it is sorted and everything left is at least as large as what was merged, those can be copied over as they are.

On the example, with i pointing into first and j into second:

1 against 1: not less, so take the one from second. Output [1].
1 against 3: take 1 from first. Output [1, 1].
4 against 3: take 3. Output [1, 1, 3].
4 against 4: take the one from second. Output [1, 1, 3, 4].
4 against 17: take 4. Then 8 against 17: take 8. Now first is used up.
Copy the rest of second: 17. The output is [1, 1, 3, 4, 4, 8, 17].

Step by step

Create the output. result is an empty Vec<i32> made with Vec::new() and declared let mut, because values will be pushed into it.
Declare the indices. i and j are mutable and start at 0usize. A vector is indexed with usize, and the suffix on the literal fixes the type.
Main loop. Run while i < first.len() && j < second.len(), so it stops as soon as either vector has no unused elements.
Take from first. When first[i] < second[j], push first[i] and increment i.
Otherwise take from second. Push second[j] and increment j. This branch also covers equal values.
Drain first. A loop while i < first.len() pushes what is left of first.
Push and advance inside it: result.push(first[i]) and i += 1.
Drain second. A loop while j < second.len() does the same for second. At most one of the two drain loops runs, because the main loop ended when one vector ran out.
Push and advance inside it as well.
Return. End with result, without a semicolon and without return.

The solution in Rust

impl Solution {
    fn merge(first: Vec<i32>, second: Vec<i32>) -> Vec<i32> {
        let mut result: Vec<i32> = Vec::new();
        let mut i = 0usize;
        let mut j = 0usize;
        while i < first.len() && j < second.len() {
            if first[i] < second[j] {
                result.push(first[i]);
                i += 1;
            } else {
                result.push(second[j]);
                j += 1;
            }
        }
        while i < first.len() {
            result.push(first[i]);
            i += 1;
        }
        while j < second.len() {
            result.push(second[j]);
            j += 1;
        }
        result
    }
}

Rust details worth knowing:

Ownership. The parameters are owned Vec<i32> values, so the function owns both inputs. Reading an element such as first[i] copies an i32, which is why no clone() is needed.
&& short-circuits. Both bounds are checked before anything is indexed, so first[i] and second[j] are always in range inside the loop.
usize everywhere. len() returns a usize, and so must the indices. Mixing in an i32 index doesn't compile without a cast.
Growth of the vector. push reallocates now and then as the vector fills, but the cost averages out to constant time per push. Calling Vec::with_capacity(first.len() + second.len()) would reserve the space up front.
Slices for the tail. A drain loop can be replaced by result.extend_from_slice(&first[i..]), which copies the rest of the vector in one call. The loops in the lesson show the same idea explicitly.

Complexity

Time: O(n + m). Every iteration of every loop pushes one element and moves one index forward, and each index only moves forward. The total number of iterations is exactly n + m.

Space: O(n + m). The output holds all n + m numbers. Apart from it, the function uses two indices.

Edge cases and common mistakes

One input is empty. With first = [] the main loop doesn't start, the first drain loop is skipped, and the second one copies all of second. [] and [2, 5] give [2, 5].
Both inputs empty. The result is an empty vector.
One input entirely smaller. [5, 6] and [1, 2] give [1, 2, 5, 6]: the main loop empties second, then the first drain loop copies first.
Forgetting the drain loops. Without them, the leftover elements are lost. The example would end at [1, 1, 3, 4, 4, 8] and drop the 17.
Duplicates. Equal values are all kept. The < test sends ties to the else branch, which takes the element from second first. For plain integers it makes no difference which equal copy goes first.
Unsorted input. The merge relies on both inputs being sorted. With unsorted input the result can come out unsorted.

Testing

[1, 4, 8] and [1, 3, 4, 17] give [1, 1, 3, 4, 4, 8, 17].
[] and [2, 5] give [2, 5].
[1, 2] and [] give [1, 2].
[1, 2, 3] and [7, 8] give [1, 2, 3, 7, 8].
[5, 6] and [1, 2] give [1, 2, 5, 6].

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

Start learning free