K-Way Merge Pattern

Merging K sorted lists or arrays efficiently with a heap instead of repeated pairwise merges.

7 min readLeetCode Patterns for InterviewsCode

Why a Frontier Heap Is Enough

When you have many individually sorted sources, the next global answer can only come from the front of one of those sources. It never comes from the middle, because each source is already ordered internally. That means you do not need to compare every remaining element everywhere. You only need a structure that tells you which source currently owns the smallest visible frontier element. A min-heap over those frontiers does exactly that.

Repeatedly merging lists two at a time can work, but it revisits data more than necessary. The k-way merge pattern instead keeps one candidate from each source in a heap. Pop the smallest candidate, append it to the answer, then advance only the source it came from by pushing that source's next element. The heap always contains the minimal information needed to choose the next global element.

One candidate per source is sufficient

Each list or row contributes only its current frontier element to the heap. When that element is consumed, only that same source needs to reveal a replacement candidate.

Worked Example

Merge three sorted arrays: [1,4,7], [2,5,8], and [3,6,9]. Initialize the heap with (1, list0, index0), (2, list1, index0), and (3, list2, index0). Pop 1, append it, then push 4 from the same list. The heap now contains 2,3,4 at its frontier.

Pop 2, append it, then push 5. Pop 3, append it, then push 6. The process keeps repeating in a rhythm: pop the global smallest frontier item, then refill the heap from that item's source only. Eventually the result becomes [1,2,3,4,5,6,7,8,9]. If you only needed the fifth smallest value, you could stop after five pops.

Pop from one source, push from the same source

That one-for-one replacement rule is the easiest way to remember k-way merge. You never push arbitrary elements; you only expose the next unseen candidate from the source you just consumed.

Implementation

Gomerge-k-sorted-arrays-with-a-frontier-heap.go

47 linesLn 1, Col 1Go

The heap contains one visible frontier element per list. Popping an item advances only its own source, which keeps the global ordering correct without touching unrelated lists.

Pattern Recognition

Look for phrases like “k sorted lists,” “sorted rows,” “next smallest pair,” or “smallest range covering one element from each list.” Those problems all expose multiple ordered sources and ask for a global order or a global frontier property. If the next answer can be produced by advancing exactly one source at a time, a heap over frontier candidates is probably the right move.

Question type	Heap stores	Stop condition
Full merge	One frontier element per source	Heap becomes empty
Kth smallest across sources	One frontier element per source	After k pops
K smallest pair expansions	Best unseen pair candidates	After collecting k answers
Smallest covering range	Current chosen element per list	Heap empty or a list is exhausted

Practice Problems

#23Merge k Sorted ListsHardK-way merge · O(n log k) time · O(k) space #378Kth Smallest Element in a Sorted MatrixMediumK-way merge over rows · O(k log n) time · O(n) space #373Find K Pairs with Smallest SumsMediumK-way merge over pair expansions · O(k log min(k, n)) time · O(min(k, n)) space #632Smallest Range Covering Elements from K ListsHardK-way merge with active maximum · O(n log k) time · O(k) space

Quiz

Quiz & Practice

Question 1 / 3

Why is one frontier element per sorted source enough for k-way merge?

Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.

Stage 1 · Code

Advanced Patterns: Intervals, Heaps & Cyclic Sort