Merge Sorted Array

You are given two non-decreasing integer arrays. The first array nums1 has a length of m + n, where the first m elements are valid and the last n elements are empty placeholders. The second array nums2 has length n and is fully valid.

Your task is to merge nums2 into nums1 so that nums1 becomes fully sorted. The merge must be in-place.

A naive merge from the front overwrites data you still need. The key is to work from the end.

Function signature

func MergeSortedArray(nums1 []int, m int, nums2 []int, n int)

Inputs / outputs

• nums1: length m + n, sorted in its first m positions.
• m: number of valid elements in nums1.
• nums2: length n, sorted in all positions.
• n: number of elements in nums2.
• Return: nothing. nums1 must be modified in-place to contain the merged result.

Example

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

After merge: nums1 = [1,2,2,3,5,6]

Constraints

• 0 <= m, n <= 100_000
• len(nums1) == m + n
• nums1[0:m] is sorted
• nums2 is sorted

Core idea (near-solution)

Use three pointers from the end:

• i = m - 1 points at the last valid element of nums1.
• j = n - 1 points at the last element of nums2.
• write = m + n - 1 points at the last slot in nums1.

Invariant: everything after write is already in its final, sorted position.

At each step, place the larger of nums1[i] and nums2[j] at nums1[write], then decrement the pointer you used. This works because the largest remaining element must belong at the end.

Algorithm (step-by-step)

1. Initialize i = m-1, j = n-1, write = m+n-1.
2. While j >= 0 (there is still data to place from nums2):
   • If i >= 0 and nums1[i] > nums2[j], write nums1[i] to nums1[write], then i--.
   • Otherwise, write nums2[j] to nums1[write], then j--.
   • Always decrement write after a write.
3. When j < 0, the merge is complete.

Correctness sketch

• Invariant: everything after write is already in its final, sorted position.
• Each step moves at least one pointer, shrinking the remaining search space.
• The invariant ensures elements outside the active window are already handled correctly.
• When pointers meet or cross, all candidates have been considered.

Trace (hand walkthrough)

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

After merge: nums1 = [1,2,2,3,5,6]

Walk:
- i=2 (3), j=2 (6), write=5 -> place 6: nums1=[1,2,3,0,0,6], j=1, write=4
- i=2 (3), j=1 (5), write=4 -> place 5: nums1=[1,2,3,0,5,6], j=0, write=3
- i=2 (3), j=0 (2), write=3 -> place 3: nums1=[1,2,3,3,5,6], i=1, write=2
- i=1 (2), j=0 (2), write=2 -> place 2 from nums2: nums1=[1,2,2,3,5,6], j=-1 stop

Pitfalls to avoid

• Merging from the front (overwrites nums1 data).
• Forgetting that nums1 has extra capacity at the end.
• Stopping when i < 0 (you still must copy remaining nums2 elements).

Complexity

• Time: O(m + n)
• Extra space: O(1)

Implementation notes (Go)

• Modifying nums1[i] updates the caller's slice (the underlying array is shared).
• Always check i >= 0 before reading nums1[i].