Merge Sorted Array Algorithm

Two sorted arrays. Merge them into one sorted array — in place, inside the first array.

The catch: nums1 has extra space at the end (filled with zeros) to hold the result. You must modify nums1 directly, not return a new array.

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

The intuition

If you merge from the front, you'll overwrite elements in nums1 before you've used them. So merge from the back.

Start three pointers at the ends: one at m-1 in nums1, one at n-1 in nums2, and one at m+n-1 (the last position). Compare the two candidates, place the larger one at the back, move the pointers.

The code

var merge = function(nums1, m, nums2, n) {
    let p1 = m - 1;
    let p2 = n - 1;
    let p = m + n - 1;

    while (p2 >= 0) {
        if (p1 >= 0 && nums1[p1] > nums2[p2]) {
            nums1[p] = nums1[p1];
            p1--;
        } else {
            nums1[p] = nums2[p2];
            p2--;
        }
        p--;
    }
};

Why merge from the back?

Working backwards means you're filling positions that are currently zeros — empty space. No data gets overwritten before it's been placed. When p2 goes below zero, the remaining elements in nums1 are already in their correct positions.

Complexity

• Time: O(m + n) — each element is placed exactly once.
• Space: O(1) — in-place, no extra arrays.

Trade-offs

This is the optimal solution. The only subtlety is remembering to merge backwards. A naive approach (merge into a temp array, copy back) works but wastes O(m + n) space for no reason.