Merge Two Sorted Arrays

Problem: Given two sorted arrays nums1 (size m+n, with m elements) and nums2 (size n), merge nums2 into nums1 in-place in sorted order.

Approach 1: Extra Space (Naive)#

This is the classic merge step from Merge Sort. Use two pointers — one in each array — and always append the smaller of the two pointed-to elements into a temporary result array. Once one array is exhausted, append the remaining elements from the other. Finally, copy the result back into nums1. The approach is simple and correct but requires O(m+n) extra space.

Create a temp array, merge both sorted arrays into it, then copy back.

void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    vector<int> temp;
    int i = 0, j = 0;
    while (i < m && j < n) {
        if (nums1[i] <= nums2[j]) temp.push_back(nums1[i++]);
        else temp.push_back(nums2[j++]);
    }
    while (i < m) temp.push_back(nums1[i++]);
    while (j < n) temp.push_back(nums2[j++]);
    for (int k = 0; k < m + n; k++) nums1[k] = temp[k];
}

• TC: O(m + n)
• SC: O(m + n) — extra temp array

Approach 2: Two Pointers from End (Optimal)#

Fill nums1 from the back using two pointers starting at the last valid elements of each array. Since nums1 has n empty slots at the end, we can place elements in-place without overwriting unvisited elements.

void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    int i = m - 1;
    int j = n - 1;
    int idx = nums1.size() - 1;

    while (j >= 0) {
        if (i >= 0 && nums1[i] > nums2[j]) {
            nums1[idx--] = nums1[i--];
        } else {
            nums1[idx--] = nums2[j--];
        }
    }
}

Why it works: The write pointer (idx) always stays ahead of or equal to i, so we never overwrite an element before it's been placed.

Once j < 0, all remaining nums1 elements are already in their correct positions.

• TC: O(m + n)
• SC: O(1)

Approach 3: Gap Method (Shell Sort idea)#

The gap method adapts the Shell Sort idea to merge two arrays without any extra buffer. The key insight is that by comparing pairs of elements a fixed "gap" apart (spanning across both arrays using index arithmetic) and swapping out-of-order pairs, then repeatedly halving the gap, we progressively sort the combined sequence in-place. Each full pass at a given gap takes O(m+n) time, and the number of passes is O(log(m+n)), giving the overall complexity. The trade-off is that this is slower than the two-pointer approach but works when the two arrays are truly separate and we cannot exploit the pre-allocated slots in nums1.

Used when both arrays are separate (without the extra buffer). Repeatedly compare and swap elements that are gap apart, halving the gap each iteration (gap = ceil(total/2)).

void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    int total = m + n;
    int gap = (total + 1) / 2;

    auto get = [&](int idx) -> int& {
        return idx < m ? nums1[idx] : nums2[idx - m];
    };

    while (gap > 0) {
        for (int left = 0, right = gap; right < total; left++, right++) {
            if (get(left) > get(right))
                swap(get(left), get(right));
        }
        if (gap == 1) break;
        gap = (gap + 1) / 2;
    }
}

• TC: O((m + n) log(m + n))
• SC: O(1)
• When to use: When the two arrays are truly separate and you cannot use the extra buffer trick from Approach 2.

Comparison#