EasyArraysTwo PointersSorting

Merge Sorted Array

2 approaches, code in every language

Two integer arrays are given in non-decreasing order. The first array has spare room at its tail sized to hold the second array's contents: its real length is m, followed by n zero placeholders, while the second array has length n.

Merge the two so the first array ends up holding all m + n values in non-decreasing order, and do the work in place rather than returning a new array.

Example 1

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3

Output: [1,2,2,3,5,6]

The placeholder zeros in nums1 get overwritten by the merged order.

Example 2

Input: nums1 = [1], m = 1, nums2 = [], n = 0

Output: [1]

Constraints

nums1.length == m + n
0 ≤ m, n ≤ 200
-10^9 ≤ nums1[i], nums2[j] ≤ 10^9

Copy Then Sort

Drop the second array into the tail of the first and sort the whole thing.

Loading animation…

Intuition

The simplest correct idea ignores that both inputs are already ordered. Copy every element of the second array into the trailing placeholder slots of the first, so the first array now holds all m + n values in some order. A single sort then puts everything in non-decreasing order. It wastes the pre-sorted structure but is easy to reason about and hard to get wrong.

Algorithm walkthrough

1Copy the n values from the second array into positions m through m + n - 1 of the first array.
2Sort the entire first array.
3The first array now contains all values in sorted order.

Implementation

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        for i in range(n):
            nums1[m + i] = nums2[i]
        nums1.sort()

Time

O((m + n) log (m + n))

Space

O(1)

In place aside from the sort's own overhead; it ignores that the inputs were already sorted.

Three Pointers From the Back

Fill the first array from its last slot backward, always placing the larger of the two current tail elements.

Loading animation…

Intuition

Writing from the front would overwrite values we still need, so instead fill from the back where the free placeholder slots already sit. Keep a pointer at the last real element of each array and a write pointer at the very end of the first array. At each step, compare the two candidates and copy the larger one into the write slot, stepping that pointer back. Because we always take the biggest remaining value and place it at the highest unfilled position, nothing important is ever clobbered, and the merge finishes in a single reverse pass.

Algorithm walkthrough

1Set i to the last real index of the first array (m - 1), j to the last index of the second (n - 1), and k to the final slot (m + n - 1).
2While elements remain in the second array, compare nums1[i] with nums2[j].
3Copy the larger of the two into position k, then move that source pointer and k backward.
4If the first array runs out (i < 0), the remaining second-array values simply flow into place.
5Once j drops below zero, any leftover first-array values are already in their correct positions.

Implementation

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        i = m - 1
        j = n - 1
        k = m + n - 1
        while j >= 0:
            if i >= 0 and nums1[i] > nums2[j]:
                nums1[k] = nums1[i]
                i -= 1
            else:
                nums1[k] = nums2[j]
                j -= 1
            k -= 1

Time

O(m + n)

Space

O(1)

A single reverse pass with no extra memory.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Priority Queues

After the pattern

Now solve one you haven't seen.

Merge Into the Padded Log is our own problem on the technique behind Merge Sorted Array: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free