Merge Sorted Array

The safe space is at the end, so the merge should run from the end.

A left-to-right merge can overwrite values in nums1 before you have compared them. The reliable Merge Sorted Array solution uses backward two pointers: compare the largest remaining values and place the larger one in the rightmost open position.

Read the contract before choosing a direction

The input has two sorted arrays, but only part of nums1 is active data:

• nums1[:m] contains its meaningful sorted values.
• nums1[m:] is reserved capacity for the result. Its placeholder values are not input.
• nums2[:n] contains the second sorted array.
• nums1 has length m + n.
• The merged array must be written into nums1 in place.

For example:

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

The active inputs are [1, 2, 3] and [2, 5, 6]. The zeros at the end are storage, not values to merge.

That layout determines the algorithm's direction. The free positions are at the back, so fill the result from right to left. This lets us write into the reserved suffix before touching values in the meaningful prefix that still need to be read.

Maintain three indices:

• i: the last unprocessed value in the active prefix of nums1
• j: the last unprocessed value in nums2
• k: the next position to fill in the final array

They begin at:

i = m - 1
j = n - 1
k = m + n - 1

At each step, the larger of nums1[i] and nums2[j] belongs at nums1[k].

Why backward two pointers are safe

The baseline solution is straightforward: copy the active part of nums1, combine it with nums2, sort everything, and write the result back. It is useful as a small correctness reference, but it allocates another collection and sorts values that are already sorted within their original arrays.

A linear merge is enough. Because each source is sorted, its largest unprocessed value sits at its right boundary. The largest remaining value across both sources must therefore be either nums1[i] or nums2[j].

The direction matters because the input and output regions overlap. If you write from the front, the next destination may contain a value from nums1 that you have not inspected yet. Writing there destroys part of your input. Moving backward avoids that collision: the rightmost open positions are the reserved suffix, and the values already placed there no longer need to be read as source values.

This is the useful recognition cue: sorted tails provide the next choice, and capacity at the tail provides a safe destination.

Derive the three-pointer algorithm

Start with the obligations rather than memorizing a formula:

• i must visit the m meaningful values originally in nums1.
• j must visit all n values in nums2.
• k must fill the final position and then move left once per write.

The loop performs the same short sequence every time:

1. Compare the two largest unprocessed candidates.
2. Write the larger candidate at nums1[k].
3. Move the pointer for the source that supplied that value.
4. Move k one position left.

Consider the sample input:

nums1 = [1, 2, 3, 0, 0, 0]
nums2 = [2, 5, 6]

The decisive state changes are:

Comparison	Value written	Destination	Next (i, j, k)
3 vs 6	6	nums1[5]	(2, 2, 4)
3 vs 5	5	nums1[4]	(2, 1, 3)
3 vs 2	3	nums1[3]	(1, 1, 2)
2 vs 2	2 from nums2	nums1[2]	(1, 0, 1)
2 vs 2	2 from nums2	nums1[1]	(1, -1, 0)

The remaining 1 from the original nums1 prefix is already in the correct position. The final array is [1, 2, 2, 3, 5, 6].

Choosing from nums2 when the values are equal is valid. The result must be non-decreasing; it does not require equal values to preserve their source order.

The invariant and correctness argument

A pointer trick becomes dependable when its state has a precise obligation. Before every iteration, maintain this invariant:

nums1[0..i] and nums2[0..j] contain exactly the meaningful values not yet placed, while nums1[k+1:] contains the largest values already placed in final sorted order.

If i < 0, the first range is empty. The same interpretation applies to j.

Why is the next choice limited to the two boundary values? Each unprocessed region is sorted. Its largest remaining value is therefore at its right edge. The largest value across both regions must be one of those two edges.

Writing the larger edge value at k preserves correctness because:

1. It is at least as large as every other unprocessed value.
2. k is the rightmost position still waiting for a value.
3. The completed suffix remains sorted: every earlier value is no larger than the value just placed.
4. Removing the selected value shrinks one source prefix and preserves the invariant.

When nums2 is exhausted, all values that had to be inserted have been placed. Any remaining active values in nums1 are already in sorted order and can remain where they are. That is why the main loop only needs to continue while j >= 0.

Handle exhaustion explicitly

The comparison must verify that nums1 still has an active candidate:

if i >= 0 and nums1[i] > nums2[j]:

When i < 0, the only possible choice is nums2[j]. The else branch handles both that case and equality.

A common incorrect loop is:

while i >= 0 and j >= 0:

That stops as soon as either source is exhausted. If nums1 runs out first, values from nums2 still need to be copied into the open positions. Looping while j >= 0 makes that cleanup part of the normal algorithm rather than an omitted afterthought.

Important boundary cases include:

• n = 0: no values from nums2 need to be placed, so nums1 is already correct.
• m = 0: nums1 has only reserved capacity, and every result value comes from nums2.
• nums1 exhausts first: the remaining nums2 values move into the front.
• nums2 exhausts first: the remaining active nums1 values are already correctly positioned.
• Duplicates: equality is handled without breaking non-decreasing order.
• Negative values: comparisons work normally; the placeholder convention does not affect active values.
• Meaningful zeroes: a zero inside nums1[:m] is real data. A zero inside nums1[m:] is only unused capacity.

One Python-specific failure mode deserves attention. If you omit i >= 0, Python's nums1[-1] syntax will read the last element instead of raising an out-of-range error. That can produce a plausible-looking but incorrect merge. The boundary check protects the algorithm's meaning, not just its runtime.

Python implementation

def merge(nums1: list[int], m: int, nums2: list[int], n: int) -> None:
    i = m - 1
    j = n - 1
    k = m + n - 1

    # Fill nums1 from right to left until nums2 is fully placed.
    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

The function mutates nums1 and returns None.

Each state variable has one job:

• i identifies the last meaningful value still available from the original nums1 prefix.
• j identifies the last value from nums2 that must still be placed.
• k identifies the last result position not yet filled.

The strict comparison nums1[i] > nums2[j] is intentional. On equality, taking nums2[j] is just as correct and lets the algorithm use one compact else branch for equality and for an exhausted nums1 prefix.

Dry run and complexity

For the sample, the writes occur in this order:

nums1 = [1, 2, 3, 0, 0, 0]
write 6 -> [1, 2, 3, 0, 0, 6]
write 5 -> [1, 2, 3, 0, 5, 6]
write 3 -> [1, 2, 3, 3, 5, 6]
write 2 -> [1, 2, 2, 3, 5, 6]
write 2 -> [1, 2, 2, 3, 5, 6]

Each active value is consumed at most once, so the time complexity is O(m + n). The algorithm uses only three index variables and no auxiliary array, so its auxiliary space complexity is O(1). The existing capacity in nums1 is required output storage, not extra working space.

The transferable recognition rule

When a sorted input has enough capacity at a safe boundary, work from that boundary:

1. Point to the largest unprocessed value in each source.
2. Point the write index at the last result position.
3. Place the larger tail value.
4. Move the chosen source pointer and the write pointer backward.
5. Stop only after the source that must be fully inserted is exhausted.

Before coding, derive i, j, and k from the input contract. Then test m = 0, n = 0, and the case where nums1 exhausts before nums2.

The broader two-pointer lesson is compact: when the free space is at the back, compare from the back and write from the back. The memory layout is not incidental; it is part of the algorithm.