The problem
Merge sorted list B into sorted list A, which has empty space at its end. Do it in place.
Input: A = [1, 2, 3, _, _, _], B = [2, 5, 6] Output: [1, 2, 2, 3, 5, 6]
Picture it
Picture filling a parking row from the back. Compare the last real car of A with the last of B and park the bigger one in the last empty slot. Filling from the back means we never overwrite a car we still need.
Short version: the full lesson (brute force, complexity, edge cases and a quiz) is still being written. The animation is complete.
The key idea
Three pointers from the end. O(m + n).
Python solution
def merge(a, m, b, n):
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] = b[j]; j -= 1
k -= 1In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.