Skip to content
Tutorials Center
My learning

Topics

Lesson 110 of 225 ยท Heaps

Merging K Sorted Lists

Merge k sorted lists with a min-heap in O(N log k) time: brute force first, the heap solution, heapq.merge, external merge sort and the smallest range problem.

You already know how to merge two sorted lists: keep one pointer in each list, compare the two front items, and take the smaller one. That is the heart of merge sort. But real systems often have many sorted inputs at once: a search engine combining result lists from dozens of servers, a database merging sorted runs written to disk, a log viewer interleaving files from many machines.

This lesson solves the general problem: given k sorted lists with N items in total, produce one sorted list. We start with the obvious approaches, then use a min-heap to get O(N log k), which is the best you can do with comparisons alone. Then we look at two famous relatives: merging data that does not fit in memory, and the "smallest range" problem.

The problem

TEXT
lists[0] = [1, 4, 9]
lists[1] = [2, 3, 8, 10]
lists[2] = [5, 6]

merged   = [1, 2, 3, 4, 5, 6, 8, 9, 10]      (N = 9 items, k = 3 lists)

Every input list is already sorted. The question is how to use that fact so we do less work than sorting from scratch.

Approach 1: concatenate and sort

The shortest solution ignores the sortedness: glue all lists together and sort.

  • Time: O(N log N), because the sort sees N items.
  • Space: O(N) for the combined list.

It is correct and often good enough in practice (Python's Timsort even detects existing sorted runs, as you will see in Shell Sort and Timsort). But it throws away information, and it needs everything in memory at once.

Approach 2: merge one list at a time

Merge list 0 with list 1, then merge the result with list 2, and so on. Merging two lists of sizes a and b costs O(a + b).

If all k lists have about N/k items, the accumulated list grows: the first merge touches 2N/k items, the second 3N/k, and so on up to N. The total is roughly (2 + 3 + ... + k) ร— N/k, which is O(N ร— k). For k = 1,000 lists that is 1,000 times more work than needed, because early items are copied again and again.

Python Brute force: merge one list at a time

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Approach 3: the heap

Think about what you need at each step. The next item of the output is the smallest of the current front items of all k lists. A min-heap is a structure that gives you the smallest of a changing set in O(log k).

The algorithm:

  1. Put the first item of every list in a min-heap, remembering which list it came from and its index there.
  2. Pop the smallest entry and append it to the output.
  3. If that list has a next item, push it.
  4. Repeat until the heap is empty.
TEXT
heap holds one front item per list (value, list, index)

lists:  A = [1, 4, 9]   B = [2, 3, 8, 10]   C = [5, 6]

heap: (1,A) (2,B) (5,C)       pop 1  -> out [1]      push A's 4
heap: (2,B) (4,A) (5,C)       pop 2  -> out [1,2]    push B's 3
heap: (3,B) (4,A) (5,C)       pop 3  -> out [1,2,3]  push B's 8
heap: (4,A) (5,C) (8,B)       pop 4  -> out [1,2,3,4] push A's 9
...

The heap never holds more than k items, so each push and pop costs O(log k). Every one of the N items is pushed once and popped once, which gives O(N log k) time and O(k) extra space (plus the output).

Why store the list number and index? The heap only compares tuples. Putting the value first means the smallest value wins. If two values tie, Python compares the next tuple element, so we include the list number as a tie-breaker. That also guarantees the integers are compared, never the lists themselves.

Python Merge k sorted lists with a heap

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Counting the work

To see the difference, count how many heap operations we do. Each item causes one pop and at most one push, and each heap operation does about log2(k) comparisons. For k = 16 that is only 4 levels, instead of the 16-way scan you would need if you looked at every front item each time.

Python Heap merge vs scanning all fronts

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The gap widens as k grows. That is the whole point of the heap: its cost depends on log k, not k.

The built-in: heapq.merge

Python ships this exact algorithm as heapq.merge. It is lazy: it returns an iterator that yields one item at a time, so you can merge huge or even infinite sorted streams without building the result. It accepts key= and reverse=True (inputs must then be sorted in descending order).

Python heapq.merge

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Merging linked lists

The famous interview version gives you k sorted linked lists. The idea is identical; the heap holds the current node of each list. The only trap is comparing nodes: if two nodes have equal values, Python would try to compare the node objects and fail. Add a tie-breaker (the list number or a counter), exactly as in the tuple version above.

Python Merge k sorted linked lists

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Divide and conquer: another O(N log k)

You can also merge the lists in pairs, like a tournament: merge list 0 with 1, 2 with 3, and so on, then merge the results in pairs again. There are about log2(k) rounds and each round touches all N items once, so the total is again O(N log k). It needs no heap, and it is the same recurrence as merge sort (see Divide and Conquer).

Python Pairwise (tournament) merging

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

External merge: data bigger than memory

Suppose you must sort a 100 GB file but have only 4 GB of RAM. Sorting everything in memory is impossible. The classic solution is external merge sort:

  1. Run generation: read 4 GB at a time, sort it in memory, write it out as a sorted run (a file). You end up with about 25 sorted runs.
  2. k-way merge: open all runs at once, read just a small buffer from each, and merge them with a min-heap, writing the output as it is produced.

This is the same algorithm as above, with the "lists" being files. Memory use is O(k ร— buffer size), independent of N. This is how databases sort large tables and how big-data tools shuffle data. The heap keeps the number of comparisons per item at about log2(k) even for hundreds of runs.

The simulation below uses small in-memory "runs" to show the two phases.

Python External merge sort simulation

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Given k sorted lists, find the smallest range [lo, hi] that contains at least one number from each list. For lists [4, 10, 15, 24, 26], [0, 9, 12, 20], [5, 18, 22, 30], the answer is [20, 24]: it contains 24, 20 and 22.

Brute force: try every pair of values as lo and hi and check each list. That is far too slow.

Heap idea: keep one current element from each list, which is exactly the heap from before. The heap's minimum is the range's low end. Track the maximum of the current elements for the high end. The range [min, max] covers every list. To try to shrink it, advance the list that holds the minimum (the only way to raise the low end), update the maximum, and compare the new range with the best seen. Stop when a list runs out. Each of the N items enters the heap once: O(N log k) time, O(k) space.

Python Smallest range covering all lists

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Complexity summary

Method Time Extra space Notes
Concatenate + sort O(N log N) O(N) Simple; ignores sortedness
Merge one at a time O(N k) O(N) Re-copies early items repeatedly
Min-heap of k fronts O(N log k) O(k) Streams; the standard answer
Pairwise (tournament) O(N log k) O(N) No heap needed
heapq.merge O(N log k) O(k) Lazy iterator

Because each output item needs about log2(k) comparisons to be placed among k candidates, O(N log k) is the best possible for a comparison-based k-way merge.

Common mistakes

  • Pushing the whole list instead of the front item. The heap must hold one entry per list, not N entries.
  • Forgetting the tie-breaker when the payload is a node or custom object: equal values then cause TypeError.
  • Not handling empty lists (and the empty input). Skip empty lists when seeding the heap.
  • Calling sorted() on a heapq.merge result and assuming it saved work. Consume the iterator lazily if memory matters.
  • Using the heap when k = 2. The simple two-pointer merge is faster and clearer.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is the time complexity of merging k sorted lists with N items in total using a min-heap?

    Every one of the N items is pushed and popped once, and each heap operation costs O(log k) because the heap holds at most k items.
  2. 2. What does the heap contain at any moment during the merge?

    The next output item is always the smallest of the current fronts, so the heap holds at most one item per list.
  3. 3. Why do heap entries include the list number as the second tuple element?

    The list number tells you which list to advance, and it breaks ties between equal values so Python never has to compare the payload objects.
  4. 4. What is special about heapq.merge compared with building a list and sorting it?

    heapq.merge expects sorted inputs and yields results one at a time, so it can merge streams larger than memory.
  5. 5. In the external merge sort of a huge file, what is the second phase?

    After sorting memory-sized runs, the runs are merged with a k-way merge that reads only a small buffer from each.

Summary

  • Merging k sorted lists with N total items: sorting everything costs O(N log N), merging one by one costs O(N k).
  • A min-heap holding one front item per list gives O(N log k) time and O(k) extra space.
  • Push (value, list number, index) tuples so ties never compare payload objects.
  • heapq.merge is the lazy, built-in version; pairwise tournament merging reaches the same bound without a heap.
  • External merge sort writes sorted runs to disk, then k-way merges them: memory use does not depend on N.
  • The smallest-range problem uses the same heap, tracking the maximum of the current fronts.

Next: Fibonacci, Binomial and d-ary Heaps