Merge Sorted Array In Place: Fill From the Back

Merging two sorted arrays into a new third array is the easy half of merge sort. The interview version adds one constraint that changes everything: the first array already has empty slots at the end, and the merged result has to land inside it, with no extra array. Start writing at the front and you destroy values you have not read yet. Start at the back and the problem disappears. That one reversal is the whole trick, and it is worth understanding why it is safe rather than memorising it.

The problem it solves

You get a with m real values followed by n spare slots, and b with n values. Both are sorted. Afterwards a must hold all m + n values in sorted order.

The obvious approaches all cost something. Copying b into the spare slots and calling a sort is O((m + n) log (m + n)) and ignores the fact that both inputs are already sorted. Merging into a fresh array and copying back is O(m + n) time but O(m + n) extra space. Merging forwards in place requires shifting every remaining value of a one step right each time a value from b goes in, which is O(m · n) in the worst case.

The goal is linear time, constant extra space, and no shifting at all.

The intuition

Look at where the free space is: at the end of a. The largest value of the whole merge belongs in the last slot, and the largest value is one of the two tails, a[m - 1] or b[n - 1]. So compare the tails, write the bigger one into slot m + n - 1, and step that pointer left. Then repeat with the next free slot.

Three pointers do all the work:

• i points at the last unread value of a.
• j points at the last unread value of b.
• k points at the next slot to write, starting at the very end.

Why can this never overwrite something unread? At every moment, the number of free slots to the right of i equals the number of unread values in b, which is j + 1. Writing one value uses one free slot and consumes one unread value, so k stays exactly j + 1 places ahead of i. The write position can only catch up with i when b is empty, and at that moment the loop stops.

That also explains the early exit. When b runs out, whatever is still unread in a is already sitting in its final place: those values are the smallest in the merge, they were sorted to begin with, and nothing has moved them. When a runs out first, the loop simply keeps copying from b.

This is the two-pointer pattern run from the right-hand end, one of the variants listed on the patterns cheat sheet.

Watch it run

The animation merges a = [1, 4, 7, _, _] with b = [3, 5]. It opens with the warning: a holds three values and two spare slots, b holds two, and writing at the front would trample a. First comparison: the tails are 7 against 5, and the bigger one takes the last free slot. Next, 5 is the bigger tail, so it drops into slot 3. Then the tails are 4 against 3, and 4 moves back. Then 3 is the bigger tail and drops into slot 1. Now b is empty, and whatever is left in a, the 1 at slot 0, is already below everything written, so the loop stops there. The closing frame sums it up: one pass, no shifting, and not one extra array allocated.

The code

The lesson's merge, with the two edge cases that trip people up, an empty a and an empty b:

def merge(a, m, b, n):
    i, j, k = m - 1, n - 1, m + n - 1
    while j >= 0:                          # stop when b is used up
        if i >= 0 and a[i] > b[j]:
            a[k] = a[i]                    # a's tail is bigger: move it back
            i -= 1
        else:
            a[k] = b[j]                    # b's tail is bigger (or a is empty)
            j -= 1
        k -= 1
    return a

print(merge([1, 4, 7, 0, 0], 3, [3, 5], 2))   # [1, 3, 4, 5, 7]
print(merge([0, 0, 0], 0, [2, 5, 6], 3))      # [2, 5, 6]
print(merge([1, 2, 3], 3, [], 0))             # [1, 2, 3]

The same loop run forwards, to show what goes wrong. The 4 and the 7 are overwritten before they are read, and the output contains three copies of 3:

def merge_forwards(a, m, b, n):
    i = j = k = 0
    while j < n:
        if i < m and a[i] <= b[j]:
            a[k] = a[i]
            i += 1
        else:
            a[k] = b[j]                    # overwrites a[k] before it is read
            j += 1
        k += 1
    return a

print(merge_forwards([1, 4, 7, 0, 0], 3, [3, 5], 2))   # [1, 3, 3, 3, 5]

Counting writes shows the early stop at work. When everything in b is larger, only n writes happen; when everything in b is smaller, every value of a has to move:

def merge_counted(a, m, b, n):
    i, j, k, writes = m - 1, n - 1, m + n - 1, 0
    while j >= 0:
        if i >= 0 and a[i] > b[j]:
            a[k] = a[i]
            i -= 1
        else:
            a[k] = b[j]
            j -= 1
        k -= 1
        writes += 1
    return writes

print(merge_counted([1, 2, 3, 0, 0], 3, [8, 9], 2))   # 2
print(merge_counted([7, 8, 9, 0, 0], 3, [1, 2], 2))   # 5

Checked against sorted() on 3,000 random pairs, including empty arrays, negatives and duplicates, with the write count held to at most m + n:

import random

random.seed(22)
ok = True
for _ in range(3000):
    m, n = random.randint(0, 12), random.randint(0, 12)
    left = sorted(random.randint(-20, 20) for _ in range(m))
    right = sorted(random.randint(-20, 20) for _ in range(n))
    a = left + [0] * n
    ok &= merge(a, m, list(right), n) == sorted(left + right)
    ok &= merge_counted(left + [0] * n, m, right, n) <= m + n
print(ok)                                   # True

The complexity

• Time: O(m + n). Each loop iteration writes one value and moves k one step left, and there are at most m + n slots.
• Space: O(1) extra. The merge happens inside the space a already owns.
• Writes: between n and m + n. Only values of a that are larger than some value of b ever move.

Where it goes wrong

• Looping while i >= 0 instead of j >= 0. If a runs out first, the remaining values of b are never copied. The loop must be driven by b.
• Dropping the i >= 0 guard. With i at -1, Python reads a[-1], the last slot, and silently compares against garbage instead of raising an error.
• Using >= for the comparison. It still sorts correctly, but taking from b on ties keeps the merge stable in the sense that values from a stay before equal values from b. That matters when records carry more than a key.
• Returning a new list. The question usually says "modify a in place"; building sorted(a[:m] + b) passes the examples and fails the constraint.

When it shows up in interviews

It is a common warm-up, and it is often the first question where the interviewer asks "can you do it without extra space?" after a working answer. It tests whether you can reason about the order of reads and writes, which comes back in rotating an array in place and the Dutch national flag partition. The merge step itself is the heart of merge sort, and the linked-list version, where no shifting problem exists, is merge two sorted lists.

How to say it in an interview

"Both arrays are sorted and the free space is at the end of a, so I fill from the back. I keep i on the last real value of a, j on the last value of b, and k on the last slot. Each step, the bigger of the two tails goes into slot k, and I move that pointer and k left. It is safe because the gap between k and i always equals the number of values left in b, so the write position never reaches an unread value. When b is empty I stop, because what remains in a is already in place. That is O(m + n) time and O(1) extra space, with no shifting."