cf.completefrontend
HEAPS & PRIORITY QUEUES · CORE

K-way merge

Merge several sorted lists into one by keeping the current front item of each list in a min-heap and always taking the smallest.

Time O(N log k)Space O(k)5 practice problemsStep-through picture

The idea

Merging two sorted lists is easy: compare their front items and take the smaller one. With k lists you would compare k front items every time, which is slow when k is big.

A min-heap does that comparison for you. Put the first item of each list in the heap, along with which list it came from (row) and its position in that list (col). Pop the smallest; it is the next item of the merged result. Then push the next item from the same list, so the heap again holds one front item per list.

The heap never holds more than k items, so each step costs O(log k), whatever the total number of items.

An everyday example

Several checkout lines merging into one door

Several lines of people stand in order of their ticket numbers, and everyone must go through one door in ticket order. A guard looks only at the person at the front of each line, waves through the lowest ticket, and then looks at the new front person of that line. The guard never has to look further back in any line.

How the example maps to the code
In the exampleIn the code
The front person of each lineone heap entry per list: { value, row, col }
Waving through the lowest ticketheap.pop() and merged.push(value)
The next person steps up in that linepush lists[row][col + 1]
A line that is now emptycol + 1 is not less than lists[row].length

From the slow way to k-way merge

  1. The obvious way is to join all the lists and sort the result: O(N log N) for N items in total. That throws away work that was already done, because every list is sorted. Merging two sorted lists takes only O(N): compare their front items and take the smaller.
  2. With k lists, the same idea says: look at the k front items and take the smallest. Scanning k fronts for every output item costs O(N × k), which is slow with hundreds of lists. The scan repeats almost the same work each time, because only one front changes after each take.
  3. A group where you take the smallest and then add one new item is exactly what a min-heap does well. Keep one entry per list in a heap: the front value, the list's index row, and the position col. Taking the smallest is a pop, and replacing it with the next item of the same list is a push, each O(log k).
  4. row and col are what make it work: after a pop, you know which list to read next, and where. Put every list's first item in the heap, pop and output the smallest, push the next item from the same list, and repeat until the heap is empty: that loop is k-way merge.

How it works

  1. Make a min-heap ordered by value.
  2. Push the first item of every non-empty list as { value, row, col: 0 }.
  3. While the heap is not empty, pop the smallest entry and add its value to merged.
  4. If its list has another item at col + 1, push that item with the same row.
  5. When the heap is empty, every item of every list has been added in order.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function mergeSortedLists(lists) {
  2. const heap = new MinHeap((a, b) => a.value - b.value);
  3. lists.forEach((list, row) => {
  4. if (list.length > 0) heap.push({ value: list[0], row, col: 0 });
  5. });
  6. const merged = [];
  7. while (heap.size > 0) {
  8. const { value, row, col } = heap.pop();
  9. merged.push(value);
  10. if (col + 1 < lists[row].length) {
  11. heap.push({ value: lists[row][col + 1], row, col: col + 1 });
  12. }
  13. }
  14. return merged;
  15. }

How fast it is

TimeO(N log k)
Extra memoryO(k)

Each of the N items goes through a heap that holds at most k entries, one per list. The output list is not counted.

  • Best caseO(N)

    There is only one list, or one non-empty list: the heap holds one entry, every push and pop is O(1), and the merge is a plain copy.

  • Average caseO(N log k)

    Each item is pushed and popped once on a heap of up to k entries.

  • Worst caseO(N log k)

    Many lists of similar length, so the heap stays full with k entries for most of the run, and each pop sinks through all log₂ k levels.

Common mistakes

  • Pushing whole lists into the heap at the start. The heap then holds all N items and you lose the O(log k) benefit.
  • Forgetting to store which list an item came from. After popping, you can't tell which list to take the next item from.
  • Pushing empty lists' first items, which are undefined. Skip empty lists.
  • Leaving ties to chance when the output order of equal values matters. Add row as a second compare key.

When to use it

Look for these clues in a problem:

  • You get several sorted lists, feeds, or files and need one sorted result.
  • You need the k-th smallest item across several sorted lists or a sorted grid.
  • You need the smallest range or pairs that come from several sorted sources.
  • The data is too large to combine and sort at once, but each part is sorted.

Check yourself

Answer each one in your head first, then open it.

Why does the heap never hold more than k entries?

It holds at most one entry per list: each pop removes a list's entry, and at most one push adds the next item from that same list.

Why must each entry remember row and col?

After a pop, the code must fetch the next item from the same list. Without row and col, it can't tell which list that was or where to read next.

In the trace, why does the heap shrink after 9 is popped?

9 was the last item of list 1, so col + 1 < lists[1].length is false and nothing is pushed.

How many heap operations does merging 10 lists of 1,000 items take?

Each of the 10,000 items is pushed once and popped once: 20,000 operations, each on a heap of at most 10 entries.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 5 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The loop keeps two rules. First, the heap holds exactly one entry for each list that still has unused items, and that entry is the list's first unused item. Second, merged is sorted, and every unused item is at least as big as the last item of merged.

Putting every non-empty list's first item in the heap makes the first rule true, and merged starts empty. Each loop pops the smallest entry. Because each list is sorted, a list's first unused item is its smallest unused item, so the smallest entry in the heap is the smallest unused item overall. Appending it keeps merged sorted, and pushing the next item from the same row keeps the first rule.

Each loop uses up exactly one item, so after N loops every item is in merged and the heap is empty. By the second rule, merged then holds all N items in sorted order.

Going deeper

3 more ideas

Why the smallest front item is the next one overall

Each list is sorted, so its front item is its smallest remaining item. The smallest remaining item overall must be the front of some list. The heap holds exactly the front of every list that still has items, so its top is the smallest remaining item overall.

Breaking ties

When two lists have the same front value, the heap may return either one first. If the output must be unique (for example, items from the first feed before items from the second when times match), compare row as a second key: (a, b) => a.value - b.value || a.row - b.row.

Time and memory

With N items in total across k lists, each item is pushed and popped once on a heap of at most k entries. That is O(N log k) time and O(k) extra memory besides the output. Concatenating and sorting would be O(N log N).

Work it by hand

Every step in a table, with why

Merge four sorted lists, one of them empty. Heap values are listed smallest first, but the heap keeps them in heap order.

lists = [[3, 8, 12], [1, 9], [], [4, 5, 14]]

StepPopped valuerow, colPushedHeap valuesmergedWhy
1--3, 1, 41, 3, 4[]Each non-empty list puts its first item in the heap. List 2 is empty, so it adds nothing.
211, 09 from list 13, 4, 9[1]1 is the smallest front. List 1 has another item at col + 1, so 9 takes its place.
330, 08 from list 04, 8, 9[1, 3]List 0's front 3 comes out, and its next item 8 goes in.
443, 05 from list 35, 8, 9[1, 3, 4]List 3's front 4 comes out, and 5 replaces it.
553, 114 from list 38, 9, 14[1, 3, 4, 5]List 3 wins twice in a row. Its next item, 14, joins the heap.
680, 112 from list 09, 12, 14[1, 3, 4, 5, 8]List 0 gives 8, and its last item, 12, joins.
791, 1nothing12, 14[1, 3, 4, 5, 8, 9]9 was the last item of list 1, so nothing is pushed and the heap shrinks to 2 entries.
8120, 2nothing14[1, 3, 4, 5, 8, 9, 12]List 0 is now used up too.
9143, 2nothingempty[1, 3, 4, 5, 8, 9, 12, 14]The last item. The heap is empty, so the loop ends.

The result is [1, 3, 4, 5, 8, 9, 12, 14]. Each of the 8 items was pushed once and popped once, and the heap never held more than 3 entries, one per non-empty list.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
K-way mergeO(N log k)O(k)Many sorted lists, or streams too big to hold at once, that must become one sorted result.
Join and sortO(N log N)O(N)The lists are small, or you can't trust them to be sorted. It is one line of code.
Scan all fronts each stepO(N · k)O(1)There are only 2 or 3 lists, so scanning the fronts costs less than heap bookkeeping.
Merge in pairsO(N log k)O(N)You already have a two-list merge and don't mind building the arrays for each round.

Extra memory: O(k) for the heap. The output merged takes O(N), which is the answer itself and isn't counted as extra.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for K-way merge and the other approaches, on a scale where each line up is 10 times more steps.
  • K-way merge, Join and sort, Merge in pairs O(N log k)
  • Scan all fronts each step O(N · k)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
K-way merge339,96620 million
Join and sort339,96620 million
Scan all fronts each step1001 million1 trillion
Merge in pairs339,96620 million

Inputs that need care

5 tricky inputs
No lists: lists = []
The heap stays empty, the loop never runs, and it returns [].
Empty lists among full ones, as in the trace
The list.length > 0 check skips them at the start. Without it, the heap gets an entry with value: undefined, and subtracting undefined gives NaN, which breaks the heap order.
One list: lists = [[2, 6, 9]]
The heap holds one entry at a time, so the merge just copies the list.
Equal values in different lists: [[2, 7], [2, 3]]
It returns [2, 2, 3, 7], but which 2 comes first isn't fixed. Add a.row - b.row as a second key to always take the lower row first.
A list that isn't sorted: [[5, 1], [3]]
The merge doesn't check. Every item still comes out, but not in order. Sort or check each list first if the input can't be trusted.

Variations and follow-ups

Twists interviewers add

Merging linked lists

With k sorted linked lists, put the head nodes in the heap, and after popping a node, push its next. The node itself plays the role of row and col, and no new arrays are needed: you just relink the nodes.

The k-th smallest across lists

Stop after k pops instead of emptying the heap. The cost is O(k log m) for m lists. The same works on a grid whose rows are sorted: treat each row as one list.

Smallest range that covers every list

Keep one entry per list and also track the largest value now in the heap. The range from the heap's top to that largest value contains one item from every list. Pop the top, push the next item from its list, update the largest, keep the narrowest range seen, and stop when any list runs out.

Merging in pairs

Merge the lists two at a time in rounds, like merge sort: k lists become k / 2, then k / 4. Each round touches all N items and there are log k rounds, so it is also O(N log k), without a heap.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "merge k sorted lists", "several sorted feeds", "k-th smallest in a sorted matrix", or "smallest range that includes an item from each list".
  • Say what each heap entry stores and why: "the value, which list it came from, and its position, so after popping I know what to push next".
  • Give the cost in terms of both sizes: O(N log k) time for N items in k lists, and O(k) heap space. It beats O(N log N) because the heap only ever holds one item per list.
  • Test by hand: an empty input, an empty list among full ones, a single list, and equal values in two lists.
  • A common follow-up: "what if the lists are files too big for memory?". Answer: the same loop works as a stream. Read a file's next item only when its entry is popped, and write each output item as it comes out. This is how external merge sort combines sorted chunks.

Where frontend code uses it

The same idea in real UI code
  • A unified inbox or activity feed merges items from several sources (comments, mentions, likes), each already sorted by time.
  • A log viewer merges sorted log streams from several services into one timeline.
  • Paginated results from several API shards can be merged page by page without loading everything at once.

Related algorithms