thesarfo

Reference

Merge Two Sorted Arrays Without Extra Space

Merging two sorted arrays in place — swapping from the ends, and the Shell Sort–style Gap Method.

views 0

Merge nums1 and nums2 (both sorted) in place, so both end up sorted, without an auxiliary array. arr1=[1,3,5,7], arr2=[0,2,6,8,9] → arr1=[0,1,2,3], arr2=[5,6,7,8,9]. (LeetCode 88)

Brute force: two-pointer merge into a temporary list, then copy back — O(m+n) time, but O(m+n) extra space.

Optimal — swap from the ends: compare arr1’s largest remaining element against arr2’s smallest; if arr1’s is bigger, swap them. Repeat until one side is exhausted, then re-sort each array (they’re each “almost sorted” after the swaps).

public static void mergeTwoSortedArraysWithoutExtraSpace(long[] a, long[] b) {
    int m = a.length;
    int n = b.length;


    int left = m - 1;
    int right = 0;


    while (left >= 0 && right < n) {
        if (a[left] > b[right]) {
            long temp = a[left];
            a[left] = b[right];
            b[right] = temp;


            left--;
            right++;
        } else {
            break;
        }
    }
}

Time: O(min(n,m)) for the swap phase + O(n log n) + O(m log m) for the final sorts. Space: O(1).

Alternative optimal — the Gap Method (Shell Sort–style): start with gap = ceil((n+m)/2), compare elements gap apart across both arrays (treated as one logical array), swapping out of order pairs, then halve the gap and repeat until gap reaches 1.

public static void mergeTwoSortedArraysWithoutExtraSpace(long[] a, long[] b) {
    int n = a.length;
    int m = b.length;
    int len = n + m;
    int gap = (len / 2) + (len % 2);


    while (gap > 0) {
        int left = 0;
        int right = left + gap;


        while (right < len) {
            if (left < n && right >= n) {
                swapIfGreater(a, b, left, right - n);
            } else if (left >= n) {
                swapIfGreater(b, b, left - n, right - n);
            } else {
                swapIfGreater(a, a, left, right);
            }
            left++;
            right++;
        }


        if (gap == 1) break;
        gap = (gap / 2) + (gap % 2);
    }
}


private static void swapIfGreater(long[] a, long[] b, int ind1, int ind2) {
    if (a[ind1] > b[ind2]) {
        long temp = a[ind1];
        a[ind1] = b[ind2];
        b[ind2] = temp;
    }
}