Advance the sequence with the smaller head
Updated
Compare a[i] and b[j]. If a[i] < b[j], i++. If b[j] < a[i], j++. The smaller unused head is consumed. Equal heads are a separate policy (emit one, or both).
What to focus on
Only one pointer moves on a strict < (unless equals are defined). The larger head stays for a later comparison.
Worked examples
a smaller
a = [1, 4, 9], b = [4, 7, 9], i=0 j=0- 1<4
- i 0→1
Result: heads now 4 vs 4
b smaller
a = [1, 4, 9], b = [4, 7, 9], i=2 j=1- 9>7
- j 1→2
Result: heads now 9 vs 9
equal
a = [1, 4, 9], b = [4, 7, 9], i=1 j=0- 4==4
- policy: i++ or j++ or both
Result: heads change by the equality rule
Try it
Write advanceSmaller(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. Advance the smaller head. Print the new heads. State the equal-head rule. From (0, 0) on a = [1, 4, 9], b = [4, 7, 9] move i. From (2, 1) move j.
a and b are sorted non-decreasing. i and j are in range on both sequences.