= K-way merge algorithm
= K-way merge
{synonym}
A <k-way merge algorithm> combines $k$ sorted finite sequences into one sorted sequence. Keep the first unconsumed item from each nonempty sequence in a <min-heap>. Repeatedly remove its smallest item, emit it, and insert the next item from the same source. Every source's remaining items are at least its head, so the smallest stored head is globally safe to emit. For $N$ total entries and $k\geq2$, <heap> construction plus merging costs $O(k+N\log k)$ time and $O(k)$ auxiliary storage. Tie-breaking by source order preserves stability when the desired convention is specified.
Back to article page
