Leetcode 88. Merge Sorted Array

We are given two sorted arrays, nums1 and nums2, of lengths $m$ and $n$. The array nums1 has length $m+n$, with the last $n$ slots empty. The goal is to merge both arrays into nums1 in sorted order, in place.

The idea is to fill nums1 from the right. At each step we place the larger of the two remaining candidates into the next free slot from the end. That way we never need extra space, and we never overwrite an unmerged element of nums1.

Notation

Let

• $l$ be the index of the largest unmerged element in the original part of nums1,
• $r$ be the index of the largest unmerged element in nums2,
• $i$ be the position in nums1 where the next largest element will be written.

Initially,

Solution

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int l = m - 1;
        int r = n - 1;
        int i = m + n - 1;
        while (r >= 0) { // some positions are yet to be filled
            if (l >= 0 && nums1[l] > nums2[r]) {
                nums1[i] = nums1[l];
                l--;
            } else {
                nums1[i] = nums2[r];
                r--;
            }
            i--;
        }
    }
}

The loop only needs to run while nums2 still has elements. Once $r < 0$, every remaining prefix of nums1 is already in the correct place.

The invariant

At the start of every iteration,

Equivalently,

Counting argument

The unmerged elements are

while the remaining destination positions are $0, \dots, i$, which is $i + 1$ positions. These quantities must be equal:

and therefore

Tracking the indices

At the start we have $l + r = m + n - 2$. Each iteration decreases $i$ by one and decreases exactly one of $l$ or $r$ by one, so the gap between $l + r$ and $i$ is preserved:

Why it remains true

Initially,

During each iteration:

• $i$ decreases by $1$, and
• exactly one of $l$ or $r$ decreases by $1$.

Thus both sides of $l + r = i - 1$ decrease by exactly $1$, so the invariant is preserved.

No unread element of nums1 is overwritten

From the invariant, $l = i - r - 1$. There are two cases.

Case 1: nums2 still has elements

If $r \ge 0$, then

Therefore,

While an element from nums2 might still be inserted, the destination $i$ is strictly to the right of every unread element of nums1, whose last unread index is $l$. Writing to nums1[i] cannot overwrite nums1[l] or any other unread element of the original nums1.

Case 2: nums2 is exhausted

If $r = -1$, then

Therefore,

This equality is safe. There are no elements left in nums2, so the remaining elements of nums1 are already in their correct positions.