22 minute read

“Combining order from chaos, one element at a time.”

TL;DR

Merge K sorted lists by efficiently finding the minimum among K list heads at each step. A min-heap of size K gives O(N log K) time. Divide-and-conquer pairs lists like merge sort, also O(N log K), without a heap. Naive sequential merging is O(N*K) because early lists participate in too many merges. The K-way merge pattern powers external sorting in databases, log aggregation, LSM-tree compaction and merging sorted shards in data pipelines. See also Median of Two Sorted Arrays and batch processing pipelines.

1. Problem Statement

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

Example 1:

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
  1->4->5,
  1->3->4,
  2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6

Example 2:

Input: lists = []
Output: []

Example 3:

Input: lists = [[]]
Output: []

Constraints:

  • k == lists.length
  • 0 <= k <= 10^4
  • 0 <= lists[i].length <= 500
  • -10^4 <= lists[i][j] <= 10^4
  • lists[i] is sorted in ascending order.
  • The sum of lists[i].length will not exceed 10^4.

2. Intuition

This problem tests your understanding of several key concepts:

  1. Heap (Priority Queue): Efficiently find the minimum among k elements.
  2. Divide and Conquer: Recursively merge pairs of lists.
  3. Linked List Manipulation: Pointer management.

The key insight is that at any point, we need to pick the smallest element among the heads of all k lists. A min-heap gives us O(log k) access to the minimum.

3. Approach 1: Brute Force (Collect All, Sort, Rebuild)

Algorithm:

  1. Traverse all lists and collect all values into an array.
  2. Sort the array.
  3. Create a new linked list from the sorted array.
from typing import List, Optional

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

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        nodes = []
        
        # Collect all values
        for lst in lists:
            while lst:
                nodes.append(lst.val)
                lst = lst.next
        
        # Sort
        nodes.sort()
        
        # Rebuild linked list
        dummy = ListNode(0)
        curr = dummy
        for val in nodes:
            curr.next = ListNode(val)
            curr = curr.next
        
        return dummy.next

Complexity:

  • Time: O(N log N) where N is total number of nodes.
  • Space: O(N) to store all values.

4. Approach 2: Compare One by One

Algorithm:

  1. Compare the head of each list.
  2. Pick the minimum.
  3. Move the pointer of the selected list forward.
  4. Repeat until all lists are exhausted.
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        dummy = ListNode(0)
        curr = dummy
        
        while True:
            min_idx = -1
            min_val = float('inf')
            
            # Find the minimum head
            for i, lst in enumerate(lists):
                if lst and lst.val < min_val:
                    min_val = lst.val
                    min_idx = i
            
            if min_idx == -1:
                break
            
            # Add to result
            curr.next = lists[min_idx]
            curr = curr.next
            lists[min_idx] = lists[min_idx].next
        
        return dummy.next

Complexity:

  • Time: O(N × k) where k is the number of lists. For each node, we scan k lists.
  • Space: O(1) (excluding output).

5. Approach 3: Min-Heap (Priority Queue)

Algorithm:

  1. Push the head of each list into a min-heap.
  2. Pop the minimum node from the heap.
  3. Add it to the result.
  4. Push the next node from that list into the heap.
  5. Repeat until the heap is empty.
import heapq

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        # Handle edge case
        if not lists:
            return None
        
        # Min-heap: (value, index, node)
        # Index is used as a tiebreaker to avoid comparing ListNode objects
        heap = []
        
        for i, lst in enumerate(lists):
            if lst:
                heapq.heappush(heap, (lst.val, i, lst))
        
        dummy = ListNode(0)
        curr = dummy
        
        while heap:
            val, idx, node = heapq.heappop(heap)
            curr.next = node
            curr = curr.next
            
            if node.next:
                heapq.heappush(heap, (node.next.val, idx, node.next))
        
        return dummy.next

Complexity:

  • Time: O(N log k). Each of N nodes is pushed and popped once. Each operation is O(log k).
  • Space: O(k) for the heap.

6. Approach 4: Divide and Conquer

Algorithm:

  1. Pair up lists and merge each pair.
  2. Repeat until only one list remains.
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        if not lists:
            return None
        
        while len(lists) > 1:
            merged = []
            for i in range(0, len(lists), 2):
                l1 = lists[i]
                l2 = lists[i + 1] if i + 1 < len(lists) else None
                merged.append(self.mergeTwoLists(l1, l2))
            lists = merged
        
        return lists[0]
    
    def mergeTwoLists(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0)
        curr = dummy
        
        while l1 and l2:
            if l1.val <= l2.val:
                curr.next = l1
                l1 = l1.next
            else:
                curr.next = l2
                l2 = l2.next
            curr = curr.next
        
        curr.next = l1 if l1 else l2
        return dummy.next

Complexity:

  • Time: O(N log k). We merge k lists in log k rounds. Each round processes N nodes.
  • Space: O(k) for the list of partial results in this iterative version. Writing each round’s results back into the input array instead brings the extra space down to O(1); a recursive version uses an O(log k) stack.

All four solutions above were checked against each other on randomized inputs, including empty lists and duplicates.

7. Complexity Comparison and Lower Bound

Why the heap gives O(N log k):

  • With k lists, the heap never holds more than k elements.
  • Each node is pushed once and popped once, O(log k) each.
  • Total: O(N log k).

Why divide and conquer gives O(N log k): the merge tree has log2(k) levels, and each level touches every element once.

Approach Time Extra space
Brute Force (Sort All) O(N log N) O(N)
Compare One by One O(N × k) O(1)
Min-Heap O(N log k) O(k)
Divide and Conquer O(N log k) O(k), or O(1) in place

Lower bound: If the k lists each hold N/k elements, the number of different ways they can interleave is the multinomial coefficient N! / ((N/k)!)^k. A comparison-based merge must distinguish all of them, so it needs at least log2 of that many comparisons, which works out to about N log2 k. O(N log k) is therefore optimal for comparison-based merging.

When k is small (e.g., k = 10): All approaches are similar. When k is large (e.g., k = 10000): Avoid the O(N × k) scan; use the heap or divide and conquer.

8. Detailed Walkthrough

Example: lists = [[1,4,5],[1,3,4],[2,6]]

Min-Heap Approach (heap contents shown as the underlying array):

Initial Heap: [(1, 0, node1), (1, 1, node2), (2, 2, node3)]

Iteration 1:

  • Pop (1, 0, node1). Add to result: 1.
  • Push (4, 0, node1.next).
  • Heap: [(1, 1, node2), (2, 2, node3), (4, 0, node4)]

Iteration 2:

  • Pop (1, 1, node2). Add to result: 1.
  • Push (3, 1, node2.next).
  • Heap: [(2, 2, node3), (4, 0, node4), (3, 1, node5)]

Iteration 3:

  • Pop (2, 2, node3). Add to result: 2.
  • Push (6, 2, node3.next).
  • Heap: [(3, 1, node5), (4, 0, node4), (6, 2, node6)]

… and so on

Final Result: 1 → 1 → 2 → 3 → 4 → 4 → 5 → 6

9. Common Mistakes

  • Comparing ListNode Objects: Python’s heapq compares tuples. If two values are equal, it compares the next tuple element, and ListNode objects cannot be compared. Put a unique index before the node as a tiebreaker.
  • Empty Lists: Handle lists = [] or lists = [[]].
  • Null Pointer Exception: Always check if a node exists before accessing node.val.
  • Off-by-One in Divide and Conquer: When pairing lists, handle an odd number of lists.

10. Variants

10.1 Merge K Sorted Arrays

Same problem with arrays instead of linked lists: use indices instead of pointers.

import heapq

def mergeKSortedArrays(arrays):
    heap = []
    
    for i, arr in enumerate(arrays):
        if arr:
            heapq.heappush(heap, (arr[0], i, 0))
    
    result = []
    
    while heap:
        val, arr_idx, elem_idx = heapq.heappop(heap)
        result.append(val)
        
        if elem_idx + 1 < len(arrays[arr_idx]):
            next_val = arrays[arr_idx][elem_idx + 1]
            heapq.heappush(heap, (next_val, arr_idx, elem_idx + 1))
    
    return result

10.2 Merge K Sorted Iterators (Streams)

If each source is a stream (a socket, a file reader, a generator) you cannot store everything. Keep one element per source in a heap of size k: pop the minimum, emit it, and pull the next element from the same source. Memory stays O(k) no matter how long the streams are, which is how log streams from k servers are merged in real time.

class MergeKIterator:
    def __init__(self, iterators):
        self.heap = []
        self.iterators = iterators
        
        for i, it in enumerate(iterators):
            try:
                val = next(it)
                heapq.heappush(self.heap, (val, i))
            except StopIteration:
                pass
    
    def __iter__(self):
        return self
    
    def __next__(self):
        if not self.heap:
            raise StopIteration
        
        val, idx = heapq.heappop(self.heap)
        
        try:
            next_val = next(self.iterators[idx])
            heapq.heappush(self.heap, (next_val, idx))
        except StopIteration:
            pass
        
        return val

# Usage
it1 = iter([1, 4, 7])
it2 = iter([2, 5, 8])
it3 = iter([3, 6, 9])

merged = MergeKIterator([it1, it2, it3])
print(list(merged))  # [1, 2, 3, 4, 5, 6, 7, 8, 9]

In production Python you rarely need to write this yourself: the standard library’s heapq.merge(*iterables, key=None) does exactly this lazily.

10.3 Custom Comparator

Merge k lists of complex objects, for example log entries sorted by timestamp:

import heapq
from dataclasses import dataclass, field

@dataclass(order=True)
class LogEntry:
    timestamp: float
    message: str = field(compare=False)
    source: str = field(compare=False)

def mergeLogStreams(streams):
    heap = []
    
    for i, stream in enumerate(streams):
        if stream:
            entry = stream[0]
            heapq.heappush(heap, (entry, i, 0))
    
    result = []
    
    while heap:
        entry, stream_idx, elem_idx = heapq.heappop(heap)
        result.append(entry)
        
        if elem_idx + 1 < len(streams[stream_idx]):
            next_entry = streams[stream_idx][elem_idx + 1]
            heapq.heappush(heap, (next_entry, stream_idx, elem_idx + 1))
    
    return result

A general template that accepts any sorted iterables and a key function:

import heapq

def k_way_merge(sources, key=lambda x: x):
    """Merge any number of sorted iterables into one sorted list."""
    iterators = [iter(s) for s in sources]
    heap = []
    for i, it in enumerate(iterators):
        for elem in it:  # first element, if any
            heap.append((key(elem), i, elem))
            break
    heapq.heapify(heap)
    
    result = []
    while heap:
        _, i, elem = heapq.heappop(heap)
        result.append(elem)
        for nxt in iterators[i]:  # next element from the same source, if any
            heapq.heappush(heap, (key(nxt), i, nxt))
            break
    return result

print(k_way_merge([[1, 4], iter([2, 3]), (0, 5)]))  # [0, 1, 2, 3, 4, 5]

10.4 Kth Smallest Element Across K Sorted Lists

Run the heap merge and stop after popping k elements: O(k log K) for K lists. The same idea solves Kth Smallest Element in a Sorted Matrix (LeetCode 378), where each row is a sorted list.

10.5 Smallest Range Covering Elements from K Lists

Problem (LeetCode 632): Given k sorted lists, find the smallest range [a, b] such that at least one element from each list is in the range.

Example:

Input: nums = [[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
Output: [20,24]

Algorithm (Min-Heap + Sliding Window):

  1. Initialize heap with the first element of each list.
  2. Track the current max.
  3. Pop the min. Range = [min, max].
  4. Push the next element from the same list.
  5. Update max if needed.
  6. Repeat until one list is exhausted.
import heapq

def smallestRange(nums):
    heap = []
    current_max = float('-inf')
    
    for i, lst in enumerate(nums):
        if lst:
            heapq.heappush(heap, (lst[0], i, 0))
            current_max = max(current_max, lst[0])
    
    best_range = [float('-inf'), float('inf')]
    
    while heap:
        current_min, list_idx, elem_idx = heapq.heappop(heap)
        
        if current_max - current_min < best_range[1] - best_range[0]:
            best_range = [current_min, current_max]
        
        if elem_idx + 1 < len(nums[list_idx]):
            next_val = nums[list_idx][elem_idx + 1]
            heapq.heappush(heap, (next_val, list_idx, elem_idx + 1))
            current_max = max(current_max, next_val)
        else:
            break  # One list exhausted
    
    return best_range

print(smallestRange([[4, 10, 15, 24, 26], [0, 9, 12, 20], [5, 18, 22, 30]]))  # [20, 24]

Complexity: O(N log k) where N is total elements.

10.6 Heap Technique: Lazy Deletion

Some variants need to remove arbitrary elements from the heap, not just the minimum. heapq cannot do that efficiently, so mark the element as deleted and discard it when it reaches the top. Count deletions so that duplicate values are handled correctly:

import heapq
from collections import Counter

class LazyHeap:
    def __init__(self):
        self.heap = []
        self.deleted = Counter()
    
    def push(self, item):
        heapq.heappush(self.heap, item)
    
    def delete(self, item):
        self.deleted[item] += 1  # item must currently be in the heap
    
    def pop(self):
        while self.heap:
            item = heapq.heappop(self.heap)
            if self.deleted[item]:
                self.deleted[item] -= 1  # skip one deleted copy
                continue
            return item
        return None

If deletions pile up, rebuild the heap from the live elements to keep its size bounded.

11. Parallel K-Way Merge

Approach: Divide and conquer parallelizes naturally.

  1. Divide: Assign pairs of lists to different workers.
  2. Merge: Each worker merges its pair.
  3. Reduce: Repeat on the results.

There are log2(k) rounds, and the merges within a round are independent.

from concurrent.futures import ThreadPoolExecutor

def parallelMergeKLists(lists, num_threads=4):
    merge_two = Solution().mergeTwoLists  # from Approach 4
    with ThreadPoolExecutor(max_workers=num_threads) as executor:
        while len(lists) > 1:
            pairs = [(lists[i], lists[i+1] if i+1 < len(lists) else None) 
                     for i in range(0, len(lists), 2)]
            futures = [executor.submit(merge_two, l1, l2) for l1, l2 in pairs]
            lists = [f.result() for f in futures]
    
    return lists[0] if lists else None

This shows the structure, not a speedup: in CPython the global interpreter lock lets only one thread run Python code at a time, so pure-Python merging gains nothing from threads. Use processes, or a language with real parallel threads, when the merge is CPU-bound. The last rounds also have less parallelism (the final round is a single merge), which is why large systems split the key range instead: each worker merges all k inputs for one range of keys.

12. Where K-Way Merge Shows Up

12.1 External Merge Sort

Merge K Sorted Lists is the core of external merge sort, used when data doesn’t fit in memory.

Scenario (illustrative): Sort 100 GB of data on a machine that can sort about 4 GB at a time in memory.

  1. Split: Divide the data into 25 chunks of about 4 GB.
  2. Sort: Load each chunk, sort it in memory, and write it back as a sorted run.
  3. Merge: Use a min-heap to merge the 25 sorted runs in one pass, reading each run through a buffer.

Optimization:

  • Multi-way merge: One 25-way merge reads the data once; repeated 2-way merges would read it about log2(25) ≈ 5 times.
  • Buffer size: Read and write in large sequential blocks to keep disk I/O efficient.
  • More runs than buffers: If there are too many runs to hold one buffer each, merge in several passes.

12.2 LSM-Tree Compaction

Storage engines built on log-structured merge trees (LevelDB, RocksDB, Cassandra) keep data in immutable sorted files. Compaction combines several sorted files into one, dropping overwritten and deleted keys along the way. That is a k-way merge.

12.3 Sharded Search and Databases

A coordinator sends a query to k shards; each shard returns its results already sorted by the ordering key (relevance score or timestamp), and the coordinator merges them. Elasticsearch’s query phase works this way: each shard returns its own top hits in sorted order and the coordinating node merges them into the global top hits. Because only the top results are needed, the merge can stop early.

Inside each Lucene index, background segment merging also combines sorted structures (term dictionaries and postings) from several segments into one.

12.4 MapReduce Reduce Side

Each mapper writes its output sorted by key. A reducer receives one sorted segment from every mapper, k-way merges them into a single key-sorted stream, then groups consecutive equal keys and calls the reduce function once per key:

from itertools import groupby

def reduce_side(segments, reduce_fn):
    """segments: k iterators of (key, value) pairs, each sorted by key."""
    merged = MergeKIterator(segments)  # one key-sorted stream
    for key, group in groupby(merged, key=lambda kv: kv[0]):
        yield reduce_fn(key, (value for _, value in group))

segments = [iter([("a", 1), ("c", 2)]), iter([("a", 3), ("b", 4)])]
print(list(reduce_side(segments, lambda k, vals: (k, sum(vals)))))  # [('a', 4), ('b', 4), ('c', 2)]

12.5 Time-Series and Log Data

A time-series store keeps each series in chunks sorted by timestamp. A query over many series k-way merges the matching chunks by timestamp, and per-chunk minimum and maximum timestamps let it skip chunks outside the query range. Log aggregation does the same with per-server log files.

12.6 ML Data Pipelines

Batch preprocessing often produces many sorted shards: examples sorted by timestamp, user ID or utterance ID, written in parallel by many workers. Time-based train/validation splits, deduplication by key and joins with another sorted dataset all want one globally sorted stream. A k-way merge over the shard readers produces it in a single streaming pass with memory proportional to the number of shards, not the data size. The same pattern merges time-stamped events (for example segment boundaries from several audio channels) into one timeline. See batch processing pipelines for the surrounding system design.

13. Performance in Practice

Asymptotics are not the whole story. On N = 200,000 random integers split into k sorted Python lists, measured with CPython 3.14 on a 2017 laptop CPU (Intel i5-7360U), best of three runs:

k Heap merge (10.1) heapq.merge sorted() of everything
10 102 ms 67 ms 16 ms
100 134 ms 94 ms 30 ms
1000 151 ms 143 ms 33 ms

The O(N log N) “brute force” wins here because CPython’s built-in sort runs in C and its Timsort algorithm detects the already-sorted runs, while the heap versions pay Python-level overhead per element. The heap merge earns its place when the data does not fit in memory, arrives as streams, or only the first few results are needed. Your numbers will differ; the ranking is what matters.

14. Can We Merge In Place?

  • Linked lists: Yes. Merging only relinks existing nodes, and bottom-up divide and conquer can write each round’s results back into the input array (lists[i] = merge(lists[i], lists[i + step])), so the extra space is O(1).
  • Arrays: In-place merging algorithms exist but are complicated and slower in practice. The usual approach accepts O(N) output space plus O(k) for the heap.
  • Special case: If the caller provides a pre-allocated output array, you avoid any allocation beyond the heap.

15. Testing and Debugging

Test Cases:

  1. Empty Input: lists = [] → Output: []
  2. Single List: lists = [[1,2,3]] → Output: [1,2,3]
  3. All Empty Lists: lists = [[], [], []] → Output: []
  4. Unequal Lengths: lists = [[1], [2,3,4], [5,6]]
  5. Duplicates: lists = [[1,1,1], [1,1], [1]]
  6. Negative Numbers: lists = [[-3,-2,-1], [-5,0,5]]
  7. Large K: k = 10000 lists with 1 element each.

Debugging Tips:

  • Print the heap after each iteration.
  • Verify that the heap property is maintained.
  • Check for off-by-one errors in index handling.

16. Interview Strategy

Step-by-Step Approach:

  1. Clarify: Ask about constraints (k, N, duplicates, etc.).
  2. Brute Force: Mention the O(N log N) sorting approach.
  3. Optimize: Introduce the heap approach (O(N log k)).
  4. Edge Cases: Handle empty lists, null nodes.
  5. Code: Write clean, bug-free code.
  6. Complexity: Analyze time and space.
  7. Follow-Up: Be ready for variants (arrays, iterators, K-th element, external sort).

Common follow-up questions:

  1. Find the Kth smallest element in K sorted lists: stop after popping k elements.
  2. Merge with O(1) extra space: possible for linked lists (section 14).
  3. External merge sort: explain runs, the k-way merge pass and buffering.
  4. Merge intervals from K streams: k-way merge the intervals by start time, then merge overlaps in one pass (see Merge Intervals).
  • Merge Two Sorted Lists (LeetCode 21)
  • Kth Smallest Element in a Sorted Matrix (LeetCode 378)
  • Find K Pairs with Smallest Sums (LeetCode 373)
  • Smallest Range Covering Elements from K Lists (LeetCode 632)
  • Ugly Number II (LeetCode 264)

18. Conclusion and Mastery Checklist

Merge K Sorted Lists is a foundational problem that appears in many real systems: external merge sort, LSM-tree compaction, sharded search, MapReduce, log aggregation and sorted-shard data pipelines.

Key Takeaways:

  • Min-Heap: O(N log k) time, O(k) space, works on streams.
  • Divide and Conquer: Same complexity, no heap, O(1) extra space for linked lists.
  • Brute Force: O(N log N), and often the fastest option in Python for in-memory data.

Mastery Checklist:

  • Implement Merge K Sorted Lists with min-heap
  • Implement with divide and conquer
  • Handle linked lists vs arrays vs iterators
  • Solve “Smallest Range Covering Elements from K Lists”
  • Solve “Kth Smallest Element in a Sorted Matrix”
  • Understand external merge sort
  • Analyze time complexity (prove O(N log k))
  • Handle edge cases (empty lists, single list, etc.)
  • Implement with custom comparator
  • Parallelize the merge

FAQ

Why is the min-heap approach optimal for merging K sorted lists?

At each step, we need the smallest element among K list heads. A min-heap provides this minimum in O(log K) time. With N total elements across all lists, the total time is O(N log K). This is optimal for comparison-based merging: there are so many possible ways to interleave K sorted lists that any comparison-based algorithm needs on the order of N log K comparisons to tell them apart.

How does divide-and-conquer compare to the heap approach?

Both achieve O(N log K) time complexity. Divide-and-conquer recursively merges pairs of lists like merge sort, reducing K lists to 1 in log K rounds, and needs no heap; for linked lists it can run with O(1) extra space. The heap approach makes a single pass and works better for streaming scenarios where elements arrive incrementally or only the first results are needed. Which is faster in practice depends on K and the runtime, so measure.

Why is naive sequential merging O(N*K) and not O(N log K)?

Merging lists one by one makes the first list participate in K-1 merge operations. If each list has N/K elements, the cumulative result grows with each merge: 2N/K, 3N/K, up to N. The total work sums to N/K(2+3+…+K) which is O(NK). Divide-and-conquer avoids this by balancing the merge tree so each element participates in exactly log K merge rounds.

What are real-world applications of K-way merge?

Databases use K-way merge for external sorting when data exceeds available memory, merging sorted runs from disk. Distributed log aggregation systems merge chronologically sorted log streams from multiple servers. LSM-tree storage engines in systems like LevelDB, RocksDB, and Cassandra use K-way merge during compaction to combine sorted string tables.