Given two integer arrays nums1 and nums2 sorted in non-decraesing order, merge nums2 into nums1 to produce a single sorted array. The array nums1 has length m + n, where the first m elements contain values to be merged and the last n elements are placeholder zeros. nums2 has length n. The modification must occur in-place within nums1.

Approach 1: Direct Concatenation with Global Sort

Copy all elements from nums2 into the vacant tail positions of nums1, then invoke the standard library sort method on the entire array.

import java.util.Arrays;

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        for (int i = 0; i < n; i++) {
            nums1[m + i] = nums2[i];
        }
        Arrays.sort(nums1);
    }
}

Complexity Analysis:

• Time: $O((m+n) \log(m+n))$ dominated by the sorting operation.
• Space: $O(1)$ auxiliary (excluding the sort implementation's stack space).

Approach 2: Linear Merge with Auxiliary Buffer

Alocate a temporary array of size m + n to store intermediate results. Traverse both input arrays with two pointers, always copying the smaller element to the buffer. After exhausting one source array, copy any remaining elements from the other. Finally, transfer the contents of the buffer back to nums1.

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int[] buffer = new int[m + n];
        int p1 = 0, p2 = 0;
        int pos = 0;
        
        while (p1 < m && p2 < n) {
            if (nums1[p1] <= nums2[p2]) {
                buffer[pos++] = nums1[p1++];
            } else {
                buffer[pos++] = nums2[p2++];
            }
        }
        
        while (p1 < m) {
            buffer[pos++] = nums1[p1++];
        }
        
        while (p2 < n) {
            buffer[pos++] = nums2[p2++];
        }
        
        System.arraycopy(buffer, 0, nums1, 0, m + n);
    }
}

Complexity Analysis:

• Time: $O(m + n)$ - each element is processed exactly once.
• Space: $O(m + n)$ - requires additional storage proportional to the total length.

Approach 3: Reverse Two-Pointer Technique

Begin merging from the end of the arrays rather than the beginning. Initialize a write pointer at position m + n - 1 (the end of the merged result), and two read pointers at positions m - 1 (last valid element of nums1) and n - 1 (last element of nums2). Compare the elements at the read pointers, place the larger value at the write pointer, and decrement the corresponding indices. This approach avoids overwriting unprocessed elements in nums1 and eliminates the need for extra space.

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int writePos = m + n - 1;
        int idx1 = m - 1;
        int idx2 = n - 1;
        
        while (idx2 >= 0) {
            if (idx1 >= 0 && nums1[idx1] > nums2[idx2]) {
                nums1[writePos--] = nums1[idx1--];
            } else {
                nums1[writePos--] = nums2[idx2--];
            }
        }
    }
}

Complexity Analysis:

• Time: $O(m + n)$ - single pass comparing elements from both arrays.
• Space: $O(1)$ - constant extra space, performing the merge entirely in-place.