K-way merge algorithm Created 2026-10-20 Updated 2026-11-05
A k-way merge algorithm combines 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 total entries and , heap construction plus merging costs time and auxiliary storage. Tie-breaking by source order preserves stability when the desired convention is specified.
Meldable min-heap 2026-10-20
A meldable heap satisfying the min-heap ordering: each parent key is no greater than its children's keys. It combines efficient merging with access to the current minimum key.
Store the array as a binary heap with min-heap order. Build it bottom-up by sifting down internal nodes in reverse order, rather than inserting all values one at a time. The sum of subtree heights is , so construction costs . Then perform minimum extractions: output the root, move the last remaining entry to the root, and sift it down to restore the heap order.
Each extraction returns the smallest remaining key, so the outputs are the smallest keys in increasing order. For a heap of current size , an extraction takes time. Hence
The tight worst-case bound for this ordinary binary heap implementation is
When the extraction term is substantial, worst-case extractions follow root-to-leaf paths of logarithmic length; when is small, the linear construction already dominates. The bound stays valid at , since . Building by separate insertions would lose the linear construction bound and is unnecessary.