k-Way Merge Time Complexity

Intuition

Merging $k$ sorted lists into one is done with a min-heap of size $k$ holding the current front element of each list. You repeatedly extract the global minimum and push the next element from the list it came from. Each of the $n$ output elements pays one extract-min plus one insert, each $O(\log k)$.

Result

$\text{cost} = \Theta(n\log k)$

• $k$ a constant $c$: $\Theta(n\log c)=\Theta(n)=O(n)$, because $\log c$ is just a constant factor.
• $k$ growing with $n$: the $\log k$ factor stays. The extreme $k=n$ (all singleton lists) turns merging into a full comparison sort, forcing the $\Omega(n\log n)$ comparison lower bound. So linear time is impossible.

Worked example

Merge $k=n$ lists of size $1$ in $O(n)$? That would sort $n$ arbitrary keys with $O(n)$ comparisons, contradicting $\Omega(n\log n)$. Hence only constant $k$ gives $O(n)$.

build min-heap from heads of all k lists   // O(k)
repeat n times:
    x = extractMin()                       // O(log k)
    output x
    insert next element of x's list        // O(log k)
// total: Theta(n log k)

Pitfall: Do not treat $k=2$ as the magic boundary. Every fixed $k$ (e.g. $3$, $10$) merges in $O(n)$ since $\log k$ collapses to a constant; the real divide is constant $k$ versus $k$ that scales with $n$.