Merge K Sorted Lists

Difficulty: Hard · Pattern: K-Way Merge · Concept: Algorithms & Data Structures — Core Data Structures

Given k already-sorted lists, merge them into a single sorted list containing every element.

Merging two sorted lists is a familiar $O(n)$ operation. The naive extension to $k$ lists — concatenate everything and call sorted() — costs $O(N \log N)$ over all $N$ total elements, throwing away the fact that each individual list was already sorted. The k-way merge pattern does better: keep a min-heap holding just the current smallest unconsumed element from each of the $k$ lists. Repeatedly pop the overall smallest, then push in the next element from whichever list it came from — the same heap/priority-queue idea beam search uses to track the top-$k$ candidates efficiently.

Your task: implement merge_k_sorted(lists) in $O(N \log k)$ time using Python's heapq, where lists is a list of $k$ sorted lists (each may be empty).

Next: Smallest Range Covering Elements from K Lists (a harder K-way-merge problem), or continue to Shortest Path in an Unweighted Graph