Merge Sorted Array

Q: What is the time complexity of merging two sorted arrays?

With two pointers it is O(m + n) , where m and n are the two lengths. Every step places one value, and no value is looked at twice. Concatenating and sorting costs O((m + n) log(m + n)) instead.

Q: How do you merge two sorted arrays in place?

When the first array has room for both at its end, fill it from the back. Compare the largest remaining values of the two arrays, write the larger one into the last free slot, and step left. Writing from the back never overwrites a value of the first array that has not been placed yet, so no second array is needed.

Q: Is merging two sorted arrays the same as the merge step of merge sort?

Yes. Merge sort splits an array in halves, sorts each half, and then joins the two sorted halves with exactly this two pointer loop. Taking the left value on a tie keeps equal values in their original order, which is what makes merge sort stable.

Q: Why not concatenate the arrays and call sort?

It gives the right answer, and in practice it is often fast. But it ignores that the inputs are already sorted and costs an extra log factor. In an interview the two pointer merge is the expected answer, because it shows you can use the order you were given.

EasyTwo pointers Sorting

+10

You get two arrays of integers, nums1 and nums2. Each one is already sorted in non-decreasing order. Return a single array that holds every value from both, also in non-decreasing order. A value that appears in both arrays appears in the result as many times as it appears in total.

Function

merge(nums1: integer-array, nums2: integer-array) → integer-array

nums1integer-array: the first sorted array
nums2integer-array: the second sorted array
Returnsinteger-array: all values of both arrays in one sorted array, of length nums1.length + nums2.length

Constraints

1 ≤ nums1.length, nums2.length ≤ 2000
-10⁵ ≤ nums1[i], nums2[j] ≤ 10⁵
nums1 and nums2 are each sorted in non-decreasing order.

Examples

Input: nums1 = [1, 4, 9]nums2 = [2, 3, 10]
Output: [1, 2, 3, 4, 9, 10]
Explanation: Read the two fronts and keep the smaller: 1, then 2 and 3 from nums2, then 4 and 9 from nums1, and 10 last. The result holds all six values.

Input: nums1 = [-5, 0, 0, 8]nums2 = [0, 6]
Output: [-5, 0, 0, 0, 6, 8]
Explanation: The 0 shows up twice in nums1 and once in nums2, so the result has three 0s. The -5 is smaller than everything in nums2 and comes first.

+13 hidden tests on Submit

Follow-up

Can you merge k sorted arrays, holding N values in total, in O(N log k) time?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

Gluing the arrays together and sorting gives the right answer, but it throws away the fact that both halves are already sorted. The smallest value left overall is always at the front of one of the two arrays. Keep one index per array, take the smaller front value each step, and one pass builds the result. This is the merge step of merge sort.

Concatenate and sort

Intuition

Put every value of nums1 and every value of nums2 into one array, then sort it. The result holds the right values, each as many times as it appeared, in the right order.

For [1, 4, 9] and [2, 3, 10] the joined array is [1, 4, 9, 2, 3, 10], and sorting gives [1, 2, 3, 4, 9, 10].

With m values in nums1 and n in nums2, a general sort costs O((m + n) log(m + n)). It works, and it is fast enough for these limits, but it does not use the sorted order you were given. The next approach does, and drops the log factor.

Algorithm

Create an array with the values of nums1 followed by those of nums2.
Sort it in increasing numeric order.
Return it.

def merge(nums1, nums2):
    return sorted(nums1 + nums2)

Two pointers, one per array

Intuition

Keep an index i into nums1 and j into nums2, both starting at 0. Everything before i and before j is already in the result. The smallest value not yet used is nums1[i] or nums2[j], because each array is sorted and its remaining values can only be larger. Append the smaller one and move that index.

On [1, 4, 9] and [2, 3, 10]: 1 beats 2, then 2 beats 4, 3 beats 4, 4 beats 10, 9 beats 10. Now nums1 is used up, so the rest of nums2, which is [10], is copied as it is. The result is [1, 2, 3, 4, 9, 10].

Every step writes one value, so the loop runs m + n times: O(m + n) time. The result array is the only extra memory.

Algorithm

Set i and j to 0 and create an empty result.
While both arrays have values left, compare nums1[i] with nums2[j].
Append the smaller one and move its index forward. On a tie, take nums1[i].
When one array runs out, append what is left of the other.
Return the result.

def merge(nums1, nums2):
    result = []
    i = j = 0
    while i < len(nums1) and j < len(nums2):
        if nums1[i] <= nums2[j]:
            result.append(nums1[i])
            i += 1
        else:
            result.append(nums2[j])
            j += 1
    # one array is used up; the rest of the other is already sorted
    result.extend(nums1[i:])
    result.extend(nums2[j:])
    return result

Pitfalls and edge cases

Most bugs show up at the moment one array runs out, or in how values are compared.

Stopping the loop as soon as one array is used up and forgetting the rest of the other. With [1, 2, 3] and [4, 5, 6], the loop ends after 1, 2 and 3, and 4, 5, 6 still have to be copied.
Reading nums1[i] after i has reached the end. Check both indices before you compare.
Dropping duplicates. [0, 0] and [0] merge to [0, 0, 0], not [0].
In JavaScript and TypeScript, sort() with no comparator orders numbers as text, so [-5, 10, 9] sorts to [-5, 10, 9]. Pass (a, b) => a - b.
In Lua and R, arrays start at 1, so both indices start at 1 and the bounds use <=.

Frequently asked questions4

What is the time complexity of merging two sorted arrays?

With two pointers it is O(m + n), where m and n are the two lengths. Every step places one value, and no value is looked at twice. Concatenating and sorting costs O((m + n) log(m + n)) instead.

How do you merge two sorted arrays in place?

When the first array has room for both at its end, fill it from the back. Compare the largest remaining values of the two arrays, write the larger one into the last free slot, and step left. Writing from the back never overwrites a value of the first array that has not been placed yet, so no second array is needed.

Is merging two sorted arrays the same as the merge step of merge sort?

Yes. Merge sort splits an array in halves, sorts each half, and then joins the two sorted halves with exactly this two pointer loop. Taking the left value on a tie keeps equal values in their original order, which is what makes merge sort stable.

Why not concatenate the arrays and call sort?

It gives the right answer, and in practice it is often fast. But it ignores that the inputs are already sorted and costs an extra log factor. In an interview the two pointer merge is the expected answer, because it shows you can use the order you were given.

Python

def merge(nums1, nums2):
    # Write code here

Test cases

Case 1

Case 2

Case 3

Input

nums1 = [1, 4, 9]
nums2 = [2, 3, 10]

Expected

[1, 2, 3, 4, 9, 10]