Merge two sequences with pointers
Updated
While both live, emit the smaller head and advance that pointer. Then drain the leftover. Output is sorted. Stability: on a[i]==b[j] emit a first (or document the opposite).
What to focus on
i and j each move at most n and m times. One output write per input element. Do not rescan either array.
Worked examples
interleave
a = [1, 4, 9], b = [4, 7, 9]- 1<4 emit 1, i++
- 4==4 emit 4(a), i++
- 4<9 emit 4(b), j++
- 7 then 9(a) then 9(b)
Result: [1, 4, 4, 7, 9, 9]
leftover a
a = [1, 4, 9], b = [4, 7]- 1 then 4(a) then 4(b) then 7
- j done, i at 9
- drain 9
Result: [1, 4, 4, 7, 9]
a all smaller
a = [1, 4], b = [7, 9]- 1<7 emit 1, 4<7 emit 4
- i done
- drain 7, 9
Result: [1, 4, 7, 9]
Try it
Write merge(a, b). 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. Emit the smaller head, then drain leftover. Return the merged array. Merge [1, 4, 9] with [4, 7, 9], with [4, 7], and [1, 4] with [7, 9].
a and b are nonempty and sorted non-decreasing.