Drain the leftover sequence
Updated
When i hits a.length, copy b[j..] into the output. When j hits b.length, copy a[i..]. The leftover is already sorted. Do not re-compare.
What to focus on
At most one side has leftover. If both pointers hit the ends together, there is nothing to drain.
Worked examples
drain a
a = [1, 4, 9], b = [4, 7], i=2 j=2 after merge walk- j done
- a[2]=9 still unused
- append 9
Result: leftover [9]
drain b
a = [1, 4], b = [4, 7, 9], i=2 j=1- i done
- b[1]=7 and b[2]=9 unused
- append 7, 9
Result: leftover [7, 9]
both done
a = [1, 4, 9], b = [4, 7, 9], i=3 j=3- no unused head
- skip drain
Result: no leftover
Try it
Write drain(a, b, i, j). a is a sorted array of integers. b is a second sorted array. i is the index on a. j is the index on b. One side may be exhausted. Append the leftover of the live side. Return that leftover. Do not re-compare. After merging [1, 4, 9] with [4, 7], leftover is [9]. After [1, 4] with [4, 7, 9], leftover is [7, 9].
a and b are sorted non-decreasing. i and j are at or past a merge walk (one side may be exhausted).