LESSON 227 OF 338 · TWO POINTERS

Merge Sorted Arrays in Go: Two Pointers in O(n + m) Time

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.

STEP 1 OF 10

Guided

Ctrl + Enter to check

Merge Sorted Arrays in Go, explained

Problem overview

The function merge receives two slices of integers, first and second, both already sorted in ascending order. It returns one new sorted slice that contains every element of both, duplicates included. For first = [1, 4, 8] and second = [1, 3, 4, 17] the result is [1, 1, 3, 4, 4, 8, 17].

The statement allows O(n + m) time and O(n + m) extra space, where n and m are the two lengths. The extra space is the result itself.

Approach: always take the smaller front element

The simplest idea is to join the two slices and sort the result. That ignores the fact that the inputs are already sorted, and sorting costs O((n + m) log(n + m)).

The sortedness gives a faster way. The smallest element not yet merged is always at the front of one of the two slices. So keep one index into each slice, i and j, compare the two front elements, copy the smaller one to the result and advance the index it came from. Each element is copied exactly once, so the whole merge takes n + m steps.

The comparison loop ends as soon as one slice is used up. The other slice may still have elements, and since it is sorted and every one of them is at least as large as everything copied so far, they can be appended as they are.

Trace of the example: the fronts 1 and 1 tie, and the tie goes to second, so the result starts [1] with j = 1. Then 1 against 3 takes first's 1, then 4 against 3 takes 3, then 4 against 4 takes second's 4, then 4 against 17 takes first's 4, then 8 against 17 takes 8. Now first is used up, and the final loop appends 17.

Step by step

Create result as an empty slice of int, with the literal []int{}. Elements will be added with append.
Create both indices i and j at 0 in one := statement.
Loop while both slices have elements left: i < len(first) and j < len(second). Go has no while, so this is a condition-only for.
If first[i] < second[j], append first[i] and advance i. append returns the grown slice, so assign it back to result.
Otherwise append second[j] and advance j. This branch also covers equal values.
Drain first with another loop that runs while i < len(first).
Append the remaining first[i] and advance i.
Drain second the same way, while j < len(second).
Append the remaining second[j] and advance j.
Return result. At most one of the two drain loops runs anything.

The solution in Go

func merge(first, second []int) []int {
    result := []int{}
    i, j := 0, 0
    for i < len(first) && j < len(second) {
        if first[i] < second[j] {
            result = append(result, first[i])
            i++
        } else {
            result = append(result, second[j])
            j++
        }
    }
    for i < len(first) {
        result = append(result, first[i])
        i++
    }
    for j < len(second) {
        result = append(result, second[j])
        j++
    }
    return result
}

The Go details worth a closer look:

append returns a slice. A slice is a view onto an array. When the array is full, append allocates a bigger one and copies the elements over, so the returned slice may point elsewhere. That is why the code always writes result = append(result, ...). Calling append and ignoring the value is a compile error.
Amortised growth. Each single append is cheap on average, because the capacity grows in large steps instead of by one. If you know the final size, make([]int, 0, len(first)+len(second)) reserves room up front and avoids the reallocations. The lesson's version doesn't need it.
Empty slice versus nil. []int{} is an empty slice, not a nil one. For two empty inputs, the function returns [] with length 0 and result == nil is false. A nil slice would also print as [] and work with len and append, but it compares equal to nil.
Parameter grouping. first, second []int gives both parameters the same type.
Nothing is modified. The function only reads from first and second. The inputs are left as they were.
Parentheses-free conditions. && joins the two conditions in the loop header. Each bound is checked before the index is used, so the code never reads past the end of a slice.

Complexity

Time: O(n + m). Every loop iteration copies one element and advances one index, and the three loops together advance the indices exactly n + m times.

Space: O(n + m). The result holds all elements. Apart from it the function stores two integers.

Edge cases and common mistakes

One input empty. merge([]int{}, []int{2, 5}) returns [2 5]. The first loop never runs, and the drain loop copies the rest.
Both empty. The result is an empty slice.
All of one slice before the other. [1, 2, 3] with [7, 8] gives [1 2 3 7 8]: the main loop empties first and the drain loop copies 7 and 8.
Duplicates. [5] with [5] gives [5 5]. Both values are kept, and nothing is removed.
Forgetting the drain loops. Without them, the leftover elements, such as the 17 in the example, are silently lost.
Ignoring the return of append. The compiler rejects it.
Using || in the main loop. The loop would then index a slice that is already used up and panic.

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, 3] and [7, 8] give [1, 2, 3, 7, 8].
[5] and [5] give [5, 5].

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

Start learning free