Merge Without Extra Space

Intuition

Merge two sorted arrays without extra space. Use gap method: compare elements gap apart, swap if out of order. Reduce gap each iteration.

Algorithm

1gap = ceil((m+n)/2).
2While gap > 0: compare pairs (i, i+gap) across both arrays, swap if out of order. gap = ceil(gap/2). Stop when gap=0.

Common Pitfalls

•Gap halves each iteration (Shell sort inspired). Handle indices carefully when gap crosses array boundary.

Merge Without Extra Space.java

Java

// Approach: Use gap method (Shell sort variant). Start with gap = ceil((n+m)/2), exchange and reduce gap.
// Time: O((n+m) log(n+m)) Space: O(1)
class Solution {
    // Function to merge the arrays.
    public void mergeArrays(int a[], int b[]) {
        int n = a.length;
        int m = b.length;

        int i = n - 1, j = 0;
        while (i >= 0 && j < m) {
            if (a[i] >= b[j]) {
                swp(a, b, i, j);
                i--;
                j++;
            } else
                break;
        }

        Arrays.sort(a);
        Arrays.sort(b);
    }

    public static void swp(int[] a, int[] b, int i, int j) {
        int t = a[i];
        a[i] = b[j];
        b[j] = t;
    }
}

Was this solution helpful?