Merge Sorted Array — Solution

Problem

Given two sorted integer arrays, merge the second into the first in-place. The first array is pre-allocated with enough trailing zeros to hold all elements from both arrays.

• Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
• Output: nums1 = [1,2,2,3,5,6] (modified in-place)
• Explanation: All six elements from both arrays are merged into one sorted sequence inside nums1.

Intuition

Both arrays are already sorted, so we can avoid re-sorting entirely by merging with two pointers. The key insight is direction: merging front-to-back overwrites valid nums1 elements before we read them. Starting from the back lets us fill the guaranteed-empty trailing slots first, always placing the current maximum without touching any unread values.

Approach 1 — Copy and Sort

Copy nums2 into the tail of nums1 then sort the whole thing. Simple but ignores the pre-sorted property entirely.

1. Write each element of nums2 into nums1 starting at index m.
2. Sort nums1 in-place.

1def merge(nums1: list[int], m: int, nums2: list[int], n: int) -> None:
2    for i in range(n):
3        nums1[m + i] = nums2[i]
4    nums1.sort()

Time: O((m+n) log(m+n)) — dominated by sorting the combined length.
Space: O(log(m+n)) — sort's internal call stack.

Approach 2 — Backwards Two Pointers

Two read pointers start at the last valid element of each array; a write pointer starts at the very last slot of nums1. On each step, place the larger of the two current elements at the write position and advance backward.

1. Initialize idx1 = m - 1, idx2 = n - 1, write_pos = m + n - 1.
2. While both read pointers are valid, compare nums1[idx1] and nums2[idx2].
3. Write the larger value to nums1[write_pos], decrement that read pointer, and decrement write_pos.
4. After the main loop, copy any remaining nums2 elements — leftover nums1 elements are already sitting in their correct positions and need no move.

1def merge(nums1: list[int], m: int, nums2: list[int], n: int) -> None:
2    idx1, idx2 = m - 1, n - 1
3    write_pos = m + n - 1
4
5    while idx1 >= 0 and idx2 >= 0:
6        if nums1[idx1] >= nums2[idx2]:
7            nums1[write_pos] = nums1[idx1]
8            idx1 -= 1
9        else:
10            nums1[write_pos] = nums2[idx2]
11            idx2 -= 1
12        write_pos -= 1
13
14    # flush remaining nums2; nums1 leftovers are already in place
15    while idx2 >= 0:
16        nums1[write_pos] = nums2[idx2]
17        idx2 -= 1
18        write_pos -= 1

Time: O(m+n) — each element is read and written exactly once.
Space: O(1) — three integer pointers, no auxiliary array.

Complexity Summary

Common Mistakes

• Merging front-to-back — writing from index 0 forward overwrites valid nums1 elements before they're read; the backwards direction exists specifically to avoid this.
• Forgetting to flush nums2 — when idx1 runs out first, nums2 still has unplaced elements; a second loop is needed. nums1 leftovers, by contrast, are already sitting in their correct positions.
• Adding an unnecessary nums1 flush — mirroring the nums2 flush with a while idx1 >= 0 loop looks symmetric but copies elements that are already where they belong.
• Off-by-one on initialization — idx1 starts at m - 1 (last valid element, not m); write_pos starts at m + n - 1 (last slot, not m + n).
• Missing the n = 0 edge case mentally — both loops exit immediately and nums1 is unchanged, which is correct; no special case needed, but interviewers often probe this.

Related Problems

• Merge Two Sorted Lists — the same two-pointer merge logic applied to linked list nodes instead of arrays
• Sort Colors — in-place rearrangement with multiple directional pointers, same "write from both ends" mindset
• Merge K Sorted Lists — generalizes pairwise merging to k sorted sequences using a heap
• Merge Intervals — merges overlapping ranges in a sorted interval list, similar sorted-order processing
• Two Sum II - Input Array Is Sorted — two-pointer technique on a sorted array, same pointer-movement discipline