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
- external sort — Sorting data too large to fit in memory by sorting it in memory-sized chunks written to disk, then merging the sorted chunks.
- heapq — Python's standard-library module of functions that treat an ordinary list as a binary min-heap.
- min-heap — A heap in which every parent is less than or equal to its children, so the minimum is at the root; a max-heap reverses the order.
- sorted merge — Combining two or more already sorted sequences into one sorted sequence by repeatedly taking the smallest front item.
Taught in
- Sorting In Real Systems: Stability, Keys And External Sort — Algorithms & Data Structures for Working Engineers
- Heaps And Priority Queues — Algorithms & Data Structures for Working Engineers