A strong answer
a holds m sorted values followed by n empty slots; b holds n sorted values. The standard merge compares the front elements of both arrays and takes the smaller, but writing to the front of a would overwrite, so fill from the back values that haven't been compared yet.
So merge from the back. Keep i = m − 1 at the last real value of a, j = n − 1 at the last value of b, and w = m + n − 1 at the last slot. While j ≥ 0, write the larger of a[i] and b[j] to a[w] (treating a as exhausted when i < 0), and move that index and w back by one. When b runs out, the remaining elements of a are already in place, so the loop can stop.
Why it is safe: before each write, w = i + j + 1, so w > i as long as any element of b remains, and the write never lands on an unread element of a. Each step places one element, so the total is O(m + n) time with O(1) extra space.
Taking from a when the two values are equal keeps equal elements from a before those from b in the result, which makes the merge stable, a property merge sort relies on.
What the interviewer is listening for
- Recognizing why the front fails and the back works.
- The loop invariant
w = i + j + 1, or an equivalent argument. - Correct handling of one array running out.
- O(m + n) time and O(1) extra space.
Common mistakes
- Merging into a new array and copying back, which works but uses O(m + n) extra space.
- Forgetting the remaining elements of
bwhenaruns out first. - Off-by-one errors in the starting indexes.