Merge K Sorted Lists in Python with heapq

Merge k sorted lists into one sorted list in O(N log k) time using a min-heap of current elements.

Medium Python 3.9+ Aug 9, 2026 Concurrency & performance 13 views 0 copies

heapq merge sorted-lists performance algorithms

Python code

20 lines

Python 3.9+

import heapq

def merge_k_sorted_lists(lists):
    heap = []
    for i, lst in enumerate(lists):
        if lst:  # only push non-empty lists
            heapq.heappush(heap, (lst[0], i, 0))
    result = []
    while heap:
        val, list_idx, elem_idx = heapq.heappop(heap)
        result.append(val)
        if elem_idx + 1 < len(lists[list_idx]):
            next_elem = lists[list_idx][elem_idx + 1]
            heapq.heappush(heap, (next_elem, list_idx, elem_idx + 1))
    return result

if __name__ == "__main__":
    lists = [[1, 4, 5], [1, 3, 4], [2, 6]]
    merged = merge_k_sorted_lists(lists)
    print(merged)

Output

stdout

[1, 1, 2, 3, 4, 4, 5, 6]

How it works

The heap holds one element from each list: the smallest unprocessed item. Each pop yields the global minimum, and we push the next element from that same list. This keeps heap size at most k, giving O(N log k) time. Ties are broken by list index to keep the heap stable. The algorithm works because each input list is already sorted, so the next candidate from a list is always its next element.

Common mistakes

Pushing tuple only with value, which breaks on ties when comparing lists
Not checking for empty lists, causing IndexError on pop
Forgetting to import heapq
Modifying the input lists while merging

Variations

Use heapq.merge(*lists) to delegate to the standard library
Convert to a single list and sort with sorted() for small inputs

Real-world use cases

Merging sorted log files from multiple services into one unified time-ordered stream.
Combining sorted database query results from shards into a single sorted API response.
Merging sorted score lists from different leaderboards for a global ranking.

Merge K Sorted Lists in Python with heapq

Python code

Output

How it works

Common mistakes

Variations

Real-world use cases

More from Concurrency & performance

Tutorials

Quizzes

Python code

Output

How it works

Common mistakes

Variations

Real-world use cases

More from Concurrency & performance

Keep learning

Tutorials

Quizzes