k-way merge

Merging k sorted sequences into one by keeping the current front item of each in a min-heap and repeatedly taking the smallest.

In more detail

Each step costs O(log k), so merging n items in total costs O(n log k). Python's heapq.merge does this lazily, reading one value at a time from each input. It is the final phase of an external sort.

Related terms

Taught in

References