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. Concatenating and sorting costs O((m + n) log(m + n)) .

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.

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

Both arrays are sorted, so the smallest value left is always at the front of one of them. Keep one index per array, take the smaller front value at each step, and one pass builds the result. This is the merge step of merge sort.

Concatenate and sort

Intuition

Join the two arrays and sort the result. It holds every value as many times as it appeared, in order. With m values in nums1 and n in nums2, the sort costs O((m + n) log(m + n)). That is fast enough for these limits, but it ignores the sorted order you were given.

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

Indices i and j mark the first unused value of each array. Append the smaller of nums1[i] and nums2[j] and move its index. Once one array is used up, what is left of the other is already in order and goes to the end as it is.

Every step writes one value, so the loop runs m + n times: O(m + n) time, with the result as 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

Stopping when 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] stays [-5, 10, 9]. Pass (a, b) => a - b.

Frequently asked questions3

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. Concatenating and sorting costs O((m + n) log(m + n)).

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 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.

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.

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

Test #1

Test #2

Test #3

Arguments

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

Expected Output

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