Merge Sorted Arrays

The Idea

Merging two sorted arrays into a third one is easy. Merging into the first one is where it bites: writing at the front tramples values you still need to read. So write from the back. The larger of the two tails takes the last free slot, and that slot always sits past everything still unread. No shifting, no second array, one pass.

Real-World Example

Restocking a shelf of dated milk cartons. The shelf is in date order and so is the delivery crate, and the shelf has empty space at the far end. Staff fill backwards from that end, newest first, so no carton is ever lifted twice.

The Code

def merge(a, m, b, n):
    i, j, k = m - 1, n - 1, m + n - 1
    while j >= 0:
        # the bigger tail takes the last free slot
        if i >= 0 and a[i] > b[j]:
            a[k] = a[i]
            i -= 1
        else:
            a[k] = b[j]
            j -= 1
        k -= 1
    return a

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

i, j, k = m - 1, n - 1, m + n - 1
while j >= 0:
  if i >= 0 and a[i] > b[j]:
      a[k] = a[i]
      i -= 1
  else:
      a[k] = ___
      j -= 1
  k -= 1