DSA Merging Two Sorted Arrays

The problem

Merging combines two sorted lists into one sorted list. Sorted means each value is at least the value before it. The first list carries spare empty cells at its end, called buffer cells.

The buffer count equals the length of the second list. The merge fills the first list in place. No third list is built.

cases = [
    ([1, 4, 9, 0, 0, 0], 3, [2, 3, 10], [1, 2, 3, 4, 9, 10]),
    ([1, 2, 3, 0, 0], 3, [8, 9], [1, 2, 3, 8, 9]),
    ([5, 6, 7, 0, 0], 3, [1, 2], [1, 2, 5, 6, 7]),
    ([0, 0], 0, [1, 2], [1, 2]),
]
for a, m, b, expected in cases:
    print('a:', a, 'real:', m, 'b:', b, '->', expected)

Intuition

The first idea merges from the front into a new list. Compare the two front values. Take the smaller one and repeat.

That merge is correct and simple. Its cost is the new list. A second trap appears if the front merge writes into the first list directly, and the next code block shows it.

a = [1, 4, 9, 0, 0, 0]
b = [2, 3, 10]
i = 0
j = 0
write = 0
steps = 0
while j < len(b) and steps < 3:
    if a[i] <= b[j]:
        a[write] = a[i]
        i += 1
    else:
        a[write] = b[j]
        j += 1
    write += 1
    steps += 1
    print('after step', steps, ':', a)
print('the 4 and 9 were overwritten before they could move')

Brute force

The safe straightforward method builds a fresh merged list. It then copies that list back over the first list. The copy back is the extra work and the extra memory.

def merge_brute(a, m, b):
    merged = []
    copies = 0
    i = 0
    j = 0
    while i < m and j < len(b):
        if a[i] <= b[j]:
            merged.append(a[i])
            i += 1
        else:
            merged.append(b[j])
            j += 1
        copies += 1
    merged.extend(a[i:m])
    merged.extend(b[j:])
    copies += len(merged)
    for index in range(len(merged)):
        a[index] = merged[index]
    return a, copies

a = [1, 4, 9, 0, 0, 0]
result, copies = merge_brute(a, 3, [2, 3, 10])
print('result:', result)
print('appends plus copy-back writes:', copies)

The optimal solution: fill from the back

The key idea is to fill from the back. The largest remaining value goes into the last free cell, so no unmerged value is ever overwritten.

def merge(a, m, b):
    i = m - 1
    j = len(b) - 1
    write = m + len(b) - 1
    while j >= 0:
        if i >= 0 and a[i] > b[j]:
            a[write] = a[i]
            i -= 1
        else:
            a[write] = b[j]
            j -= 1
        write -= 1
    return a

cases = [
    ([1, 4, 9, 0, 0, 0], 3, [2, 3, 10]),
    ([1, 2, 3, 0, 0], 3, [8, 9]),
    ([5, 6, 7, 0, 0], 3, [1, 2]),
    ([0, 0], 0, [1, 2]),
]
for a, m, b in cases:
    print(a, '+', b, '->', merge(list(a), m, list(b)))

Walkthrough

Take a = [1, 4, 9] with three buffer cells and b = [2, 3, 10]. The write index starts on the last cell. Each step places the larger of the two back values.

a = [1, 4, 9, 0, 0, 0]
b = [2, 3, 10]
i = 2
j = 2
write = 5
while j >= 0:
    if i >= 0 and a[i] > b[j]:
        print('place a value', a[i], 'at', write)
        a[write] = a[i]
        i -= 1
    else:
        print('place b value', b[j], 'at', write)
        a[write] = b[j]
        j -= 1
    write -= 1
    print('list:', a)
print('final:', a)

The placements run 10, 9, 4, 3 and 2 from the back. The value 1 never moves. It already sits in its final cell when the second list runs out.

Complexity

Time is O(m + n), where m and n are the two real lengths. Each step places one value, leftover front values of the first list stay in place, and no value is copied back.

Space is O(1). Three indices are the only extra storage, and the buffer cells are part of the input.

def placements(m, n):
    a = list(range(0, 2 * m, 2)) + [0] * n
    b = list(range(1, 2 * n, 2))
    i = m - 1
    j = n - 1
    write = m + n - 1
    count = 0
    while j >= 0:
        if i >= 0 and a[i] > b[j]:
            a[write] = a[i]
            i -= 1
        else:
            a[write] = b[j]
            j -= 1
        write -= 1
        count += 1
    return count

for m, n in [(3, 3), (6, 6), (12, 12)]:
    print('m =', m, 'n =', n, 'placements:', placements(m, n))

Edge cases and pitfalls

An empty second list needs no work. The loop condition on j ends the merge at once, and the first list is already the answer.

Leftover values of the first list need no copying when the second list runs out. Those values already sit in their final cells. Copying them anyway is harmless but wasted, and stopping early is the point of the back fill.

def merge(a, m, b):
    i = m - 1
    j = len(b) - 1
    write = m + len(b) - 1
    while j >= 0:
        if i >= 0 and a[i] > b[j]:
            a[write] = a[i]
            i -= 1
        else:
            a[write] = b[j]
            j -= 1
        write -= 1
    return a

print('b empty:', merge([1, 2, 3], 3, []))
print('a has no real values:', merge([0, 0], 0, [1, 2]))
print('all b smaller:', merge([5, 6, 7, 0, 0], 3, [1, 2]))
print('all b larger:', merge([1, 2, 3, 0, 0], 3, [8, 9]))
print('equal values:', merge([2, 4, 0, 0], 2, [2, 4]))