The Merge Problem

Given $k$ sorted lists, merge them into one sorted list. Approaches:

$1.$ Merge two at a time: merge first two, then merge result with third, etc. Time: $O(nk)$ where $n$ is total elements.

$2.$ Min-heap: always pick the smallest among current heads. Time: $O(n \log k)$. The heap approach is much faster when $k$ is large. The heap tracks the "frontier" of $k$ candidates.