K-way merge

Problem

You have k sequences that are each already sorted, and you want one sorted sequence, or just the first few items of it, or the best item that touches every sequence. The sequences may be linked lists, arrays, or streams that you can only read forward. The shape is the same in all of them: several ordered sources, and a rule that always asks for "the smallest next item across all of them".

Intuition

Picture a card game where k players each hold a sorted hand, face up, smallest on the left. The dealer wants all the cards in one sorted pile. At every step, the next card for the pile must be the smallest card overall. That card is certainly the leftmost card of some hand, since each hand is sorted, so only the k leftmost cards compete. The dealer takes the smallest of those k, and the owner's next card steps up to take its place.

Finding the smallest of k cards by scanning costs k comparisons per output card, so O(nk) in all. A min-heap holding just those k front cards finds the smallest in O(1) and repairs itself in O(log k) after one is replaced. That is the entire idea: a heap is a scoreboard for the k fingers.

Green boxes are the heads currently in the heap. Everything to their right is waiting behind a head in its own list. The diagram scrolls sideways on a narrow screen.

Mechanics

The invariant

The heap holds exactly one entry for each source that still has items: its first unread item. Each entry also carries the source index and position, so you know where to read next, and so that ties compare on integers and never on list nodes (which cannot be ordered). Every value already written to the output is no larger than every value that is still unread. Why: any unread value is either in the heap, in which case it is at least the heap minimum that was just removed, or sits behind a head in a sorted list and is at least that head. So removing the minimum head and appending it is always the correct next output, and replacing it with its successor restores the one-entry-per-source rule.

Why O(n log k)

Each of the n items is pushed once and popped once, and the heap never has more than k entries, so each heap operation is O(log k). The setup is O(k). Memory is O(k) beyond the output. Compare folding the lists in one at a time: merging a running result of growing length with each new list re-touches early items again and again, which is O(nk) for equal lists. Merging pairs in rounds like a tournament costs n per round for ⌈log₂ k⌉ rounds, which is the same O(n log k) as the heap.

Moves of items for 8 lists of 4. Folding in one by one grows with the number of lists times the total; the heap and the round-by-round merge both grow with the total times log of the number of lists.

Beyond plain merging

The heap does not need to run to completion. A news feed pops only the first ten entries. The k-th smallest in a sorted matrix pops k times. In smallest range, you also track the largest head: the heap root and that maximum bound a window that touches every list. Moving the minimum forward is the only move that can shrink the window, because the maximum cannot go down without losing a list; and as soon as one list runs out there is no window left, so the search ends.

Worked example

Merge the lists [1, 4, 7, 10], [2, 5] and [3, 6, 8]. Each row shows the value popped, the list it came from, and the heads left in the heap.

The heap held at most 3 entries, one per list, and the output is 1, 2, 3, 4, 5, 6, 7, 8, 10. When list 1 runs out after 5, its entry is simply not replaced, and the heap shrinks to 2.

Smallest range. For the lists [1, 5, 9], [2, 6, 11] and [4, 7, 8], each row is the window from the heap minimum to the running maximum, and the best window so far:

The tightest window that contains one value from every list is [4, 6]. The search stops after 7 windows, when the list that held the minimum has no next item.

Implementation

import heapq


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def merge_k_lists(lists):
    heap = []
    for i, node in enumerate(lists):
        if node:
            heap.append((node.val, i, node))   # i breaks ties so nodes are never compared
    heapq.heapify(heap)
    dummy = tail = ListNode()
    while heap:
        _, i, node = heapq.heappop(heap)
        tail.next = node
        tail = node
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))
    return dummy.next


def merge_arrays(arrays):
    heap = [(a[0], i, 0) for i, a in enumerate(arrays) if a]
    heapq.heapify(heap)
    out = []
    while heap:
        value, i, j = heapq.heappop(heap)
        out.append(value)
        if j + 1 < len(arrays[i]):
            heapq.heappush(heap, (arrays[i][j + 1], i, j + 1))
    return out


def smallest_range(arrays):
    heap = [(a[0], i, 0) for i, a in enumerate(arrays)]
    heapq.heapify(heap)
    high = max(h[0] for h in heap)
    best = (heap[0][0], high)
    while True:
        low, i, j = heap[0]
        if high - low < best[1] - best[0]:
            best = (low, high)
        if j + 1 == len(arrays[i]):
            return list(best)
        nxt = arrays[i][j + 1]
        heapq.heapreplace(heap, (nxt, i, j + 1))
        high = max(high, nxt)

The standard library already has heapq.merge(*iterables), a lazy k-way merge, which is good for real code and a fair way to check your own. The tie-break index i is the part people forget: without it, equal values make Python compare the nodes themselves and raise a TypeError.

Variations and edge cases

• Divide and conquer. Merge lists in pairs, then pairs of pairs. It matches the heap's O(n log k) time, needs no heap and reuses a plain two-list merge, which is handy for linked lists.
• News feed. Each user's recent items are a sorted source ordered newest first (so use negated timestamps or a max-heap). Stop after ten pops, and push the next item of the user you just popped from.
• Sorted matrix. Treat each row as a list and push only the first column at the start, or treat each column as a list and expand lazily; pop k times for the k-th smallest.
• Lazy output. A generator that yields after each pop never builds the full result, so the merge can run over streams larger than memory.
• Edge cases: k equal to 0, lists that are empty or None (skip them when seeding the heap), a single list, duplicate values across lists (the index tie-break keeps them in a stable order), and one very long list next to many tiny ones.

Complexity and tradeoffs

• Time: O(n log k) for n total items in k sources, plus O(k) to seed the heap.
• Space: O(k) for the heap, and O(1) extra for linked lists if you relink nodes instead of copying; the output array costs O(n) when you need it.
• Baseline. Concatenate and sort: O(n log n), a one-liner, and often fast in practice because Python's sort exploits existing runs. It ignores the sorted structure, so it is a fair first answer but not the intended one.
• When it fails. If k is 2, a plain two-pointer merge is simpler and faster. If sources are not sorted, the head is not their minimum and the heap gives wrong answers. If you only need the k smallest overall and the sources are huge, popping k times keeps the cost at O((k + m) log m) for m sources, much less than n.

Problems

The home problems show three faces of the same heap: merging linked lists, building a news feed that merges followed users' recent items, and finding the tightest range across lists. The interval problem listed below is taught on the sweep-line page but merges sorted schedules in the same way.

Medium

• 355. Design Twitter NeetCode 150 NeetCode 250
  Each user's tweets are already time-ordered, so a news feed is a k-way merge of the followed users' recent tweets.

Hard

• 23. Merge k Sorted Lists Blind 75 Grind 169 NeetCode 150 NeetCode 250
  Keep the current head of every list in a min-heap and repeatedly pop the smallest, pushing that node's successor.
• 632. Smallest Range Covering Elements from K Lists Grind 169
  Keep one pointer per list in a min-heap with the current maximum, and advance the list holding the minimum while recording the tightest range.

Also uses this pattern

These problems have a different home page, but this idea is part of their solution.

• 759. Employee Free Time Hard

Connections

This page needs the heap operations from the heaps page and the node-relinking habits from the linked-list basics page. It is the second use of a size-k heap after top-k: there the heap kept the best k items, here it keeps one item per source. The two-heaps page keeps heaps balanced around a median, and the interval pages later merge sorted events in a similar way.

Check yourself

References

• Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, chapter 2 (the MERGE procedure), chapter 6 (priority queues) and exercise 6.5-9 in the 3rd edition (merging k sorted lists with a heap in O(n lg k)).
• Knuth, The Art of Computer Programming, volume 3, section 5.4: multiway merging and tournament trees.
• Sedgewick and Wayne, Algorithms, section 2.2 (mergesort) and the "Multiway" priority-queue merge client in section 2.4.
• Skiena, The Algorithm Design Manual: the heapsort and mergesort sections of the sorting chapter, and the catalog entry on priority queues.
• Python documentation, heapq.merge and the heap tie-breaking note in the priority-queue recipes.
• The NeetCode roadmap and the Blind 75, Grind 169, NeetCode 150 and NeetCode 250 lists, used as the index of topics and problems.