Interleaving two sorted runs
To merge two sorted sequences into a single sorted sequence, you keep a pointer at the front of each input. At every step you compare the two front elements, append the smaller one to the output, and advance only the pointer you took from.
The drain step
Eventually one input runs out before the other. At that point the remaining input is already sorted, so you simply drain the rest of it onto the output without further comparisons.
- Compare the two current fronts.
- Append the smaller and advance its pointer.
- Drain whatever remains once one side empties.
Each element is appended exactly once and each pointer only moves forward, so the merge runs in a single linear pass over the combined length.
Where it appears
This merge is the combine step of merge sort, the join of two sorted lists, and the heart of merging sorted files too large to hold in memory at once.
Key idea
Merging keeps a pointer into each sorted input, repeatedly appends the smaller front and advances it, then drains the leftover, producing one sorted output in a single linear pass.