K-way Merge

Beyond two-way merge

Merging two sorted lists is O(n) with two pointers. For k sorted lists, a min-heap holding one candidate per list generalizes this: always pop the smallest, then push that list's next element.

Merge k sorted lists

Seed the heap with the first element of each list (tagged with its list/index so we know where to fetch the next value from).

import heapq

def merge_k_sorted(lists):
    heap = []
    for i, lst in enumerate(lists):
        if lst:
            heapq.heappush(heap, (lst[0], i, 0))

    result = []
    while heap:
        val, i, j = heapq.heappop(heap)
        result.append(val)
        if j + 1 < len(lists[i]):
            heapq.heappush(heap, (lists[i][j + 1], i, j + 1))
    return result

Output:

merge_k_sorted([[1,4,5],[1,3,4],[2,6]])
# [1, 1, 2, 3, 4, 4, 5, 6]

Complexity & uses

With n total elements across k lists, this runs in O(n log k) — the heap never holds more than k elements. Used for merging sorted log files, external sorting, and the 'smallest range covering k lists' family of problems.