88. Merge Sorted Array (In-Place)

# Question

You are given two integer arrays $nums1$ and $nums2$, sorted in non-decreasing order. You are also given integers $m$ and $n$, which represent the number of initialized elements in $nums1$ and $nums2$ respectively.

Merge $nums1$ and $nums2$ into a single array sorted in non-decreasing order. The final sorted array must be stored in-place inside the array $nums1$. To accommodate this, $nums1$ has a total length of $m + n$.

# Solution

# Pattern

Backward Three-Pointer Manipulation Instead of processing elements from the beginning (which forces an expensive array shift operation), compare and write elements starting from the back of the pre-allocated buffer space.

# How to Identify

• Two input data structures are provided already sorted.
• The destination container contains trailing empty padding explicitly designed to fit the incoming dataset.
• Constraints demand an in-place modification with $O(1)$ auxiliary space.

# Description

Step-by-step explanation:

• Step 1: Pointer Initialization. Create three tracking pointers:
  • p1 positioned at the end of valid data in $nums1$ ($m - 1$).
  • p2 positioned at the end of $nums2$ ($n - 1$).
  • w (write pointer) positioned at the absolute end of the $nums1$ storage buffer ($m + n - 1$).
• Step 2: Core Processing Loop. Execute a loop that runs continuously as long as there are valid uncopied elements remaining in $nums2$ ($p2 \ge 0$).
• Step 3: Evaluation & Assignment. - If p1 >= 0 and $nums1[p1] > nums2[p2]$, copy the value at $nums1[p1]$ to $nums1[w]$, then decrement p1.
  • Otherwise, copy the value at $nums2[p2]$ to $nums1[w]$, then decrement p2.
• Step 4: Shift Write Position. Decrement the write pointer w after every assignment step.
• Step 5: Implicit Completion. Once p2 drops below 0, terminate. Any remaining elements belonging to $nums1$ are already left in their correctly sorted configurations.

# The Intuition

Think of this as loading a delivery truck from back to front.

If you try to load new packages into the front of the truck ($nums1$), you would have to manually push all the existing items ($m$ elements) backward every single time to clear out space, resulting in highly inefficient work.

By starting at the very back of the truck where empty space is guaranteed ($m + n - 1$), you can compare the largest items from both sets and place them securely in position. You never have to shift any items, and you will never accidentally crush (overwrite) a package that hasn't been scanned yet.

# Complexity

# Time Complexity

$O(m + n)$. In the worst-case scenario, every item from both inputs must be individually evaluated and written into the composite layout. Each element is moved at most once.

# Space Complexity

$O(1)$. The solution edits elements completely in-place inside the pre-allocated tail space of $nums1$. No dynamic tracking collections or recursive stack contexts are used.

# Code

class Solution {
    /**
     * Merges nums2 into nums1 backwards to guarantee O(1) auxiliary space.
     */
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // Isolate pointers to avoid destroying the input method parameters
        int p1 = m - 1;        // High index of valid data in nums1
        int p2 = n - 1;        // High index of data in nums2
        int w = m + n - 1;     // Global write pointer at the back of the buffer
 
        // The process is complete the exact moment nums2 elements are exhausted.
        // If nums1 empties out early, the conditional block naturally flushes nums2 items forward.
        while (p2 >= 0) {
            if (p1 >= 0 && nums1[p1] > nums2[p2]) {
                nums1[w] = nums1[p1];
                p1--;
            } else {
                nums1[w] = nums2[p2];
                p2--;
            }
            w--; // Pull the global write tracking position backward
        }
    }
}

# Caveats

• Short-Circuit Order Check: The index out-of-bounds guard p1 >= 0 must be written prior to evaluating nums1[p1] in the conditional check expression. Reversing this order will cause a runtime exception if $nums1$ runs out of elements first.
• The Early Termination Trap: Do not write the loop boundary condition as while (p1 >= 0 && p2 >= 0). If you do, the loop will exit early if $nums1$ elements are exhausted first, leaving the remaining smaller items of $nums2$ completely missing from the front of the array.

# Concepts to Think About

• Stable Sort Consistency: Utilizing a strict inequality check (> instead of >=) ensures that the relative placement order of identical matching keys coming from different source streams remains stable.
• Hardware Cache Layouts: Iterating through sequential memory arrays from back to front reads contiguous cash blocks, which plays favorably with modern hardware architecture pre-fetching rules.
• System Buffer Architecture: This strategy mirrors lower-level operating system network ring-buffer mechanics, where structural padding spaces are pre-allocated to bypass secondary allocation bottlenecks.

# Logical Follow-up

Question: How would you resolve this problem if $nums1$ did not possess any trailing buffer padding?

Solution: To maintain $O(1)$ space without padding, you would be forced to insert from the front and shift elements downstream on insertions, degrading runtime performance to $O(m \cdot n)$. To maintain linear $O(m + n)$ time, you would have to allocate an auxiliary data array copy of size $m$, moving your auxiliary space footprint up to $O(m)$.

Question: How does the strategy shift if the input datasets are presented as two Singly Linked Lists instead of sequential memory arrays?

Solution: Linked lists allow structural modification via pointer manipulation without memory shifting overhead. A forward merge pattern is preferred here: you maintain a dummy head node and stitch the pointers together from smallest to largest. The time complexity stays $O(m + n)$, and the space complexity stays $O(1)$.