Merge Two Sorted Arrays

Merging two sorted arrays is a super-practical task you’ll do whenever you need to combine sorted streams—think merging log files, time series data, or query results. It’s also a perfect warm-up for array manipulation and two-pointer techniques in interviews.

Problem Statement

You’re given two integer arrays nums1 and nums2, sorted in non-decreasing order.

• nums1 has a length of m + n, where the first m elements hold valid data and the last n elements are set to 0 and should be ignored.

• nums2 has a length of n containing valid data.

Implement merge(nums1, m, nums2, n) to merge nums2 into nums1 in-place, resulting in one sorted array of length m + n.

1. Clarify Requirements Before Jumping Into Code

I need to nail down a few details first

• Is nums1 guaranteed to have exactly m + n slots? Yes.

• Can I use extra arrays or must this be in-place in nums1? In-place is required.

• Are the inputs always valid? Assume 0 ≤ m,n ≤ len(nums1) and both arrays sorted.

• Should I preserve the original order of equal elements? Yes—stable merge.

• What about negative numbers or duplicates? Both arrays can contain any integers, including duplicates and negatives.

2. Identify the Category of the Question

This is an array manipulation problem using the two-pointer technique. I’m merging two sorted lists in linear time, so I need to exploit their sorted order without extra memory.

3. Consider a Brute-Force Approach to Understand the Problem

The simplest, no-constraints approach: copy the first m elements of nums1 into a new list, append all elements of nums2, sort the combined list, and write back into nums1.

• Complexity: O((m+n) log(m+n)) time, O(m+n) extra space

• Correctness: Yes

• Drawback: Violates in-place and time expectations for merging sorted streams

4. Brainstorm More Solutions

A better approach exploits sorted order:

• Forward Two-Pointer with Extra Array:Maintain pointers i in nums1_copy, j in nums2, pick the smaller each time into a new array, then copy back. O(m+n) time, O(m+n) space.

• Backward Two-Pointer In-Place:Use three pointers:

  • p1 = m - 1 at end of valid nums1

  • p2 = n - 1 at end of nums2

  • write = m + n - 1 at very end of nums1Compare nums1[p1] and nums2[p2] and write the larger to nums1[write], then decrement appropriate pointers. O(m+n) time, O(1) space.

The backward in-place merge meets constraints best.

5. Discuss Trade-Offs Between Your Solutions

Approach	Time	Space	Pros	Cons
Sort Combined Array	O((m+n)log)	O(m+n)	Very simple	Not in-place; slow for large n
Forward Two-Pointer + Extra Array	O(m+n)	O(m+n)	Linear time; easy merge logic	Uses extra O(m+n) memory
Backward Two-Pointer In-Place	O(m+n)	O(1)	Linear time; in-place; minimal memory	Slightly trickier pointer logic

Backward two-pointer wins for interviews.

6. Write Pseudocode to Structure Your Thoughts

function merge(nums1, m, nums2, n):
    p1 = m - 1
    p2 = n - 1
    write = m + n - 1

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

7. Consider Edge Cases

• n = 0: no elements to merge → nums1 stays the same.

• m = 0: all merged elements come from nums2 → copy entire nums2 into nums1.

• All nums1 elements larger than nums2: back-pointer logic places nums1 first.

• All nums2 elements larger: places nums2 at end; leftover nums1 remain at front.

• Duplicates across arrays: stable ordering maintained by <= tie-break logic.

8. Write Full Code Syntax

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

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

9. Test Your Code

# Test 1: typical merge
nums1 = [1,2,3,0,0,0]; merge(nums1, 3, [2,5,6], 3)
assert nums1 == [1,2,2,3,5,6]

# Test 2: nums2 empty
nums1 = [1,2,3]; merge(nums1, 3, [], 0)
assert nums1 == [1,2,3]

# Test 3: nums1 empty region
nums1 = [0,0]; merge(nums1, 0, [1,2], 2)
assert nums1 == [1,2]

# Test 4: all nums2 smaller
nums1 = [4,5,6,0,0,0]; merge(nums1, 3, [1,2,3], 3)
assert nums1 == [1,2,3,4,5,6]

# Test 5: duplicates
nums1 = [1,1,2,0,0]; merge(nums1, 3, [1,2], 2)
assert nums1 == [1,1,1,2,2]

print("All tests passed!")

10. Key Lessons to Remember for Future Questions

• When merging two sorted lists in-place, start from the end to avoid overwriting.

• Two-pointer patterns shine in linear merging problems—identify pointers at both inputs and a write pointer.

• Edge cases (empty lists, all smaller/larger elements) often drive off-by-one bugs.

• Recognizing “sorted + merge” maps directly to two-pointer merging in O(m+n) time and O(1) extra space.