Merge Two Sorted Arrays Without Extra Space

Merge Two Sorted Arrays Without Extra Space is a classic twist on the everyday merge step. The merge itself is easy with a scratch array — the challenge is doing it in place, using only O(1) extra memory. The trick is the gap algorithm, a Shell-sort-flavored merge.

The slow way first

The textbook merge walks both arrays with two pointers and writes the smaller value into a new array of size n + m. That is clean and O(n + m) time, but it spends O(n + m) extra space — exactly what this problem forbids.

You could instead, for each element of b, insert it into its correct slot in a by shifting elements over (insertion-sort style). That uses no extra array, but the shifting makes it O(n · m) in the worst case — too slow.

The question to ask: can I fix the order in place without shifting one element at a time? Yes — by comparing elements that are far apart first, and closing that distance gradually.

The idea: compare across a shrinking gap

Treat a and b as one long virtual array of length n + m: positions 0 … n-1 live in a, positions n … n+m-1 live in b. Now run a single rule:

Pick a gap, starting at ceil((n + m) / 2). Sweep i from the left and compare the element at i with the one at i + gap. If the left one is bigger, swap them. After one full sweep, halve the gap (rounding up) and sweep again. Stop once the gap drops below 1.

Because both halves start sorted, comparing across a wide gap moves small values left and large values right in big jumps. Each smaller gap cleans up shorter-range disorder, and the final gap = 1 pass is just an adjacent sweep that guarantees full order.

Walk through it

Step through the animation. The two cells i and i + gap light up each comparison; out-of-order pairs swap and slide past each other. The gap label up top starts at 4, then shrinks to 2, then 1. By the time the gap = 1 sweep finishes, the joined view [1, 2, 3, 4, 7, 8, 9, 10] is fully sorted, split back into a and b.

Pseudocode

total = n + m
gap = ceil(total / 2)
while gap > 0:
    for i from 0 while i + gap < total:
        if element[i] > element[i + gap]:
            swap element[i] and element[i + gap]   # index into a or b as needed
    if gap == 1:
        gap = 0
    else:
        gap = ceil(gap / 2)

The Python solution

def merge(a, b):
    n, m = len(a), len(b)
    total = n + m
    gap = (total + 1) // 2
    def at(k):
        return a[k] if k < n else b[k - n]
    def put(k, val):
        if k < n: a[k] = val
        else: b[k - n] = val
    while gap > 0:
        for i in range(total - gap):
            if at(i) > at(i + gap):
                lo, hi = at(i + gap), at(i)
                put(i, lo); put(i + gap, hi)
        gap = 0 if gap == 1 else (gap + 1) // 2
    return a, b

• total = n + m is the length of the virtual concatenated array.
• gap = (total + 1) // 2 is ceil(total / 2) written with integer math.
• at(k) and put(k, val) are the bridge: index k reads or writes a when k < n, otherwise it lands in b at k - n. This is what lets us treat the two arrays as one without copying.
• The for i in range(total - gap) sweep compares every pair exactly gap apart; the if swaps when the left value is bigger.
• gap = 0 if gap == 1 else (gap + 1) // 2 halves the gap (rounding up) and ends the loop after the gap = 1 pass.

Complexity

The gap halves each round, so there are about log(n + m) rounds, and each round is a single linear sweep. That gives O((n + m) log(n + m)) time with only O(1) extra space — the whole point of the problem.

When this pattern shows up

Practice