Merge k sorted lists in Python using a heap

Merge k individually sorted lists into one sorted list in Python using a min-heap.

Medium Python 3.9+ Aug 9, 2026 Algorithms & data structures 17 views 0 copies

heapq merge sorted-list k-way-merge

Python code

28 lines

Python 3.9+

import heapq

def merge_k_sorted_lists(lists):
    heap = []
    # Push the first element of each list onto the heap
    for i, lst in enumerate(lists):
        if lst:
            heapq.heappush(heap, (lst[0], i, 0))
    
    result = []
    while heap:
        val, list_idx, elem_idx = heapq.heappop(heap)
        result.append(val)
        # If there's a next element in the same list, push it
        if elem_idx + 1 < len(lists[list_idx]):
            next_val = lists[list_idx][elem_idx + 1]
            heapq.heappush(heap, (next_val, list_idx, elem_idx + 1))
    
    return result

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

Output

stdout

Merged result: [1, 2, 3, 4, 5, 6, 7, 8, 9]

How it works

This algorithm uses a min-heap to always pop the smallest current element across all k lists. After popping, it pushes the next element from that same list into the heap. This guarantees the result is fully sorted. Each list element is pushed and popped exactly once, so the time complexity is O(N log k) where N is the total number of elements.

Common mistakes

Forgetting to store the list index in the heap tuple — you need it to know which list to pull the next value from.
Pushing the same element twice or failing to check if a list has a next element before pushing.
Assuming all input lists are non-empty — the initial loop must skip empty lists.

Variations

Use heapq.merge(*lists) for a concise one-liner that does the same thing with identical complexity.
For a small number of lists, repeatedly merge two lists at a time using the standard two-pointer merge.

Real-world use cases

Merging chunks of already-sorted on-disk data during a distributed sorting pipeline.
Combining several sorted API results or log streams into one unified chronological stream.
Implementing an external merge-sort step where individual sorted runs must be combined efficiently.

Merge k sorted lists in Python using a heap

Python code

Output

How it works

Common mistakes

Variations

Real-world use cases

More from Algorithms & data structures

Tutorials

Quizzes

Python code

Output

How it works

Common mistakes

Variations

Real-world use cases

More from Algorithms & data structures

Keep learning

Tutorials

Quizzes