Topics › Arrays › Hard

Merge two sorted arrays without extra space

Medium TUF ID 25 A2ZSDE

LeetCode ↗ Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

You are given two sorted integer arrays a of length n and b of length m. Rearrange the values in place so that, afterwards, a holds the n smallest of all n + m values in sorted order and b holds the remaining m largest, also sorted. Equivalently: if you wrote a followed by b as one array, it would be the sorted merge of the two inputs. No third array of size n + m may be used.

The LeetCode variant (merge-sorted-array) gives a a tail of m empty slots and asks you to fill them; that version is a plain backwards merge. The version here, with no spare slots, is the harder one and is what the sheets intend.

Constraints: 0 ≤ n, m ≤ 10^5, values fit in a 32-bit signed integer.

Example 1

a = [1, 4, 8, 10], b = [2, 3, 9]
after: a = [1, 2, 3, 4], b = [8, 9, 10]

The sorted merge is [1, 2, 3, 4, 8, 9, 10]; its first four values go to a, the rest to b.

Example 2

a = [4, 5, 6], b = [1, 2, 3]
after: a = [1, 2, 3], b = [4, 5, 6]

Every value in a is larger than every value in b, so the two arrays simply exchange contents.

Approach 1: Brute force

Intuition. Ignore the space restriction for a moment. The standard two-finger merge builds a sorted array of size n + m in linear time; copy its first n entries back into a and the rest into b. This is the reference solution the other approaches must match.

Algorithm.

1. Merge a and b into merged with the usual two-pointer merge.
2. Copy merged[0 .. n-1] into a and merged[n .. n+m-1] into b.

static void bruteForce(int[] a, int[] b) {
    int n = a.length, m = b.length;
    int[] merged = new int[n + m];
    int i = 0, j = 0, k = 0;
    while (i < n && j < m) merged[k++] = a[i] <= b[j] ? a[i++] : b[j++];
    while (i < n) merged[k++] = a[i++];
    while (j < m) merged[k++] = b[j++];
    for (k = 0; k < n + m; k++) {
        if (k < n) a[k] = merged[k];
        else b[k - n] = merged[k];
    }
}

Complexity. Time O(n + m): each element is moved twice. Space O(n + m) for merged, which is exactly what the problem forbids.

Approach 2: Better, swap across the boundary then sort

Intuition. In the final arrangement, every element of a is ≤ every element of b. The only elements currently violating this are large values at the end of a and small values at the start of b. Walk left from the end of a and right from the start of b; while a[left] > b[right], swap them and move both pointers. Once a[left] ≤ b[right], every remaining a element (all smaller than a[left]) is also ≤ every remaining b element, so the partition is correct. The swaps may scramble the order inside each array, so sort each one.

Why does one pass of swaps achieve the right partition? After the swaps, the elements moved into a are the smallest values of b’s prefix, and those moved into b are the largest values of a’s suffix; the stopping condition certifies that nothing left in a exceeds anything left in b. The sets are right, only the internal orders need fixing.

Algorithm.

1. left = n - 1, right = 0.
2. While both indices are valid and a[left] > b[right]: swap, left--, right++.
3. Sort a and sort b.

static void better(int[] a, int[] b) {
    int n = a.length, m = b.length;
    int left = n - 1, right = 0;
    while (left >= 0 && right < m && a[left] > b[right]) {
        swap(a, left, b, right);
        left--;
        right++;
    }
    Arrays.sort(a);
    Arrays.sort(b);
}

Complexity. Time O((n + m) + n log n + m log m): a linear swap pass and two sorts. Space O(1) extra (Java’s primitive Arrays.sort is an in-place dual-pivot quicksort).

This is already a valid in-place solution and is often accepted. Its weakness is that it throws away the fact that the inputs were sorted and pays for two full sorts.

Approach 3: Optimal, the gap method

Intuition. Treat a followed by b as one virtual array of length n + m. Shell sort’s insight is that comparing and swapping elements that are a fixed gap apart, then shrinking the gap, moves elements long distances cheaply. Start with gap = ceil((n + m) / 2), compare each position with the one gap to its right (swapping when out of order), then set gap = ceil(gap / 2) and repeat until a pass with gap = 1 has been done. Because both halves were sorted to begin with, this sequence of passes finishes the merge; the final gap = 1 pass is a single bubble sweep that fixes any remaining adjacent disorder.

The only bookkeeping is translating a virtual index p into a real one: p < n means a[p], otherwise b[p - n]. Each comparison therefore falls into one of three cases: both indices in a, both in b, or left in a and right in b.

Algorithm.

1. gap = (n + m + 1) / 2.
2. While gap > 0: set left = 0, right = gap; while right < n + m, compare the elements at virtual positions left and right, swap if the left one is larger, then advance both by one.
3. If gap == 1 stop; otherwise gap = (gap + 1) / 2.

static void optimal(int[] a, int[] b) {
    int n = a.length, m = b.length;
    int gap = (n + m + 1) / 2;                              // ceil((n + m) / 2)
    while (gap > 0) {
        int left = 0, right = gap;
        while (right < n + m) {
            if (left < n && right >= n) {                    // left in a, right in b
                if (a[left] > b[right - n]) swap(a, left, b, right - n);
            } else if (left >= n) {                          // both in b
                if (b[left - n] > b[right - n]) swap(b, left - n, b, right - n);
            } else {                                         // both in a
                if (a[left] > a[right]) swap(a, left, a, right);
            }
            left++;
            right++;
        }
        if (gap == 1) break;
        gap = (gap + 1) / 2;                                 // ceil(gap / 2)
    }
}

The swap helper works whether or not x and y are the same array:

static void swap(int[] x, int i, int[] y, int j) {
    int t = x[i];
    x[i] = y[j];
    y[j] = t;
}

Dry run on a = [1, 4, 8, 10], b = [2, 3, 9] (virtual array 1 4 8 10 | 2 3 9, length 7):

The final state is a = [1, 2, 3, 4], b = [8, 9, 10].

Complexity. Time O((n + m) log(n + m)): log(n + m) gap values, each a linear pass. Space O(1): only a handful of integers.

Why ceil and the explicit gap == 1 stop? ceil(gap / 2) guarantees the gap actually reaches 1 (integer division would jump from 1 to 0 fine, but from 3 to 1 it skips 2, and from 2 to 1 works; ceil keeps the standard Shell-sort sequence that is known to complete the merge for pre-sorted halves). Breaking after the gap == 1 pass prevents an infinite loop, since ceil(1 / 2) = 1.

Edge cases and pitfalls

• One array empty. n = 0 or m = 0 must leave both arrays untouched. In the gap method right starts at gap ≥ 1 and all comparisons fall in the “both in b” or “both in a” branch, which is a no-op on already sorted data.
• Single elements. a = [1], b = [0] becomes a = [0], b = [1]: one swap at gap = 1.
• Duplicates. Equal values are never swapped (> not >=), so a = [2, 2, 5], b = [2, 3] gives a = [2, 2, 2], b = [3, 5].
• Very unequal sizes. a = [10], b = [1, 2, 3, 4, 5] pushes 10 all the way to the end of b, through several gap passes.
• Off-by-one in the virtual index. right >= n means “in b at index right - n”. Mixing up left < n and left >= n branches silently corrupts the data; the test suite compares all three approaches against the same expected arrays.
• Forgetting the sort in approach 2. The swap pass alone leaves a = [1, 3, 2, 4]-style disorder; the sorts are part of the algorithm.

Related problems

• Merge Sorting is the ordinary merge with a temporary buffer.
• Merge two Sorted Lists merges linked lists, where relinking nodes makes “in place” easy.
• Count Inversions counts cross pairs during a standard merge.