Merge Sorted Array: The Backwards Trick

Merge Sorted Array is LeetCode problem 88 and one of the first problems on the Blind 75 list. It looks deceptively simple: merge two sorted arrays into one. You have probably done this in a merge sort implementation. But there is a twist that catches most people off guard.

You have to do it in-place. And the trick to doing it cleanly is to work backwards.

The problem

You are given two sorted integer arrays nums1 and nums2, plus their respective lengths m and n. Merge nums2 into nums1 as one sorted array.

The catch: nums1 has length m + n, with the last n positions filled with zeros as placeholders. You must not create a new array. You must modify nums1 directly.

Example: nums1 = [1, 2, 3, 0, 0, 0], m = 3, nums2 = [2, 5, 6], n = 3. After merging, nums1 should be [1, 2, 2, 3, 5, 6].

Why filling from the front does not work

Your first instinct might be to start from the beginning. Compare nums1[0] with nums2[0], place the smaller one, move the pointer. That is how merge sort does it.

The problem: if you start placing values at the front of nums1, you overwrite the original values that you still need. If nums2[0] = 2 and nums1[0] = 1, great, 1 stays. But when nums2[0] = 2 needs to go before nums1[1] = 3, you have to shift everything right. That is O(n) per insertion and O(n^2) overall.

You could copy nums1 into a temporary array first, then merge from both copies. That works in O(n) time, but uses O(m) extra space. The problem wants O(1) extra space.

The key insight: start from the back

Here is the trick. The end of nums1 is empty (those zeros are just placeholders). If you start filling from position m + n - 1 and work backwards, you never overwrite a value you still need.

Think about it: the largest values go at the end. By picking the larger of nums1[p1] and nums2[p2] at each step, you place it at the tail position and move left. The values at the front of nums1 are smaller, so they are safe until you get to them.

Three pointers:

• p1 starts at m - 1 (last real element in nums1)
• p2 starts at n - 1 (last element in nums2)
• tail starts at m + n - 1 (last position in the full array)

At each step, compare nums1[p1] and nums2[p2]. Place the larger one at nums1[tail]. Decrement the pointer you used and decrement tail. Repeat until p2 goes below zero.

Visual walkthrough

Let's trace through nums1 = [1, 2, 3, 0, 0, 0], nums2 = [2, 5, 6]. Watch the three pointers (p1 in orange, p2 in green, tail in purple) as they move from right to left.

Notice something important in step 4: when p2 goes below zero, we stop. Any remaining elements in nums1 are already in the right place because nums1 was sorted to begin with. If p1 runs out first instead, we would copy the remaining nums2 elements. But we never need to copy remaining nums1 elements since they are already sitting in nums1.

The code

Here is the clean Python solution:

def merge(nums1, m, nums2, n):
    p1 = m - 1
    p2 = n - 1
    tail = m + n - 1

    while p2 >= 0:
        if p1 >= 0 and nums1[p1] > nums2[p2]:
            nums1[tail] = nums1[p1]
            p1 -= 1
        else:
            nums1[tail] = nums2[p2]
            p2 -= 1
        tail -= 1

Let's break down why the loop condition is while p2 >= 0 and not while p1 >= 0 and p2 >= 0:

• If p2 finishes first, the remaining nums1 elements are already in place. We are done.
• If p1 finishes first, we still need to copy the remaining nums2 elements. The else branch handles this: when p1 < 0, the condition p1 >= 0 and nums1[p1] > nums2[p2] is False, so we always take the else path and copy from nums2.

That single while p2 >= 0 handles both cases cleanly.

Complexity analysis

Time: O(m + n). Each element is placed exactly once. The three pointers each move left monotonically, so the total number of steps is m + n.

Space: O(1). We only use three integer pointers. No extra arrays, no copying. Everything happens in-place inside nums1.

This is optimal. You have to look at every element at least once, so you cannot do better than O(m + n). And you cannot use less than O(1) extra space.

Edge cases to watch for

• nums2 is empty (n = 0). The while loop never executes. nums1 is already the answer.
• nums1 has no real elements (m = 0). p1 starts at -1, so we always take the else branch and copy all of nums2 into nums1.
• All of nums2 is larger than nums1. p1 never moves. We fill in from the back with nums2 values, and nums1's original elements stay in their positions.
• All of nums2 is smaller than nums1. p1 elements get shifted right first, then nums2 elements fill in the front.
• Duplicate values. The > comparison places the nums2 copy when values are equal. Either choice is correct since both produce a valid sorted array.

The Building Blocks

This problem is built from one core building block:

Two-input merge walk. You have two sorted sequences and three pointers: one for each input and one for the output position. At each step, you compare the current elements from both inputs, pick the one that belongs next, and advance the corresponding pointer. This is the same merge step from merge sort, but here we run it backwards to enable in-place operation.

This brick shows up constantly:

• Merge sort uses the exact same two-input merge, just forward into a temporary buffer.
• Merge Two Sorted Lists (LeetCode 21) applies the same logic to linked lists instead of arrays.
• Merge k Sorted Lists (LeetCode 23) extends it with a heap to pick the minimum across k inputs.
• Intersection of Two Arrays II (LeetCode 350) uses the merge walk but only keeps matching elements.

The backwards trick is specific to this problem, but the core merge walk pattern is one of the most reusable bricks in all of algorithm design. Once you can do a two-input merge without thinking, you unlock a whole family of problems.

Why you will forget this (and how to fix it)

This problem is rated Easy, and the solution is only six lines of Python. That is exactly why people forget it. You read it, think "oh that is clever, start from the back," and move on. Three weeks later, you see a merge problem in an interview and you start from the front, overwrite values, panic, and reach for a temporary array.

The insight is simple, but producing it under pressure requires having done it from memory multiple times. Spaced repetition locks it in: you type the solution from scratch today, again in two days, again in a week. After a few reps, the backwards trick is automatic. You do not think about it. You just do it.

Related posts

• The Two Pointers Pattern - The foundational two pointer technique that powers this solution and many others
• Best Time to Buy and Sell Stock - Another easy problem where a single pass with the right pointer strategy gives you O(n)

---

Visual Learner? Watch the merge operation animate with our Merge Sort Interactive Visualization.