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.
Articles by others on the same topic
The K-way merge algorithm is a generalization of the two-way merge process used in merge sort, which allows for the merging of more than two sorted lists (or arrays) into a single sorted output. The algorithm is particularly useful in contexts such as external sorting, where data sets are too large to fit into memory and are stored on disk.