Merging many sorted lists at once

You are given k lists, each holding m numbers already sorted in increasing order. Merge them into one sorted list.

Worked example#

Three lists of three:

1 4 5
1 3 7
2 6 8

Merged: 1 1 2 3 4 5 6 7 8.

The idea#

Merging two sorted lists is the familiar walk: compare the fronts, take the smaller, advance that one.

With k lists the idea is unchanged, but "compare the fronts" now means comparing k values. Scanning all k for every value written costs k per output, so n k overall, where n is k times m.

A min-heap answers "which of these is smallest" in log k. That is exactly the question, so that is the structure.

• Put the first value of every list into the heap, tagged with which list it came from.
• Pop the smallest. It is the next value of the answer.
• Push the next value from the list it came from.

The heap holds at most k things, one per list, and every value passes through once. So n log k.

The tag is the whole trick#

A bare value in the heap is useless. When you pop a 4, you need to know which list to advance, so each entry carries the value, which list it came from, and how far into that list you are.

Leaving the tag out is the usual first attempt, and it fails confusingly: the first few values come out right and then the merge runs out early or repeats itself, because nothing advanced correctly.

The alternative worth knowing#

Merge them in pairs: list 1 with 2, list 3 with 4, then merge the results, and again, until one is left. That is log k rounds, each touching all n values, so n log k as well.

Same cost, different shape, no heap. The heap wins when the lists arrive as streams rather than all at once, because it never needs to see a whole list to start.

Why not just concatenate and sort#

Because that is n log n, and log n is bigger than log k whenever there is more than one value per list. With a hundred lists of a thousand each, log k is about 7 and log n about 17, so the heap does under half the comparisons. The bigger reason is memory: the heap holds k values, not n.

Constraints#

• 1 <= k <= 100
• 1 <= m <= 1000

About the input#

A row count k, then a column count m, then the k lists, one per line.