Merge Without Extra Space

Problem Overview

Merge two sorted arrays without extra space.

See our study guide for structured GFG and LeetCode practice.

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?