CLRS Solutions | Exercise 6.5-9

Give an $O(n \lg k)$-time algorithm to merge $k$ sorted lists into one sorted list, where $n$ is the total number of elements in all the input lists. (Hint: Use a min-heap for $k$-way merging.)

The challenge of merging $k$ sorted lists is finding the global minimum among $k$ current candidates efficiently. A min-heap provides exactly this capability: it lets us extract the minimum from $k$ elements in $O(\lg k)$ time.

Think of it like merging $k$ sorted files. At any moment, we’re looking at the “front” element of each file (the smallest unprocessed element from that file). We need to repeatedly pick the smallest among these $k$ front elements and advance that file’s position.

The algorithm maintains a min-heap containing at most one element from each list (specifically, the smallest unprocessed element from each list). We repeatedly extract the minimum from the heap and insert the next element from the same list.

Algorithm

$$\textsc{Merge-K-Lists}(lists, k)$$$$\begin{aligned} 1& \quad \textbf{/\!/} \text{ n}\,\text{ is}\,\text{ total}\,\text{ number}\,\text{ of}\,\text{ elements}\,\text{ across}\,\text{ all}\,\text{ lists}\, \\ 2& \quad result\,=\,\text{new}\,\text{array}\,\text{of}\,\text{size}\,n \\ 3& \quad \\ 4& \quad \textbf{/\!/} \text{ Build}\,\text{ initial}\,\text{ min-heap}\,\text{ with}\,\text{ first}\,\text{ element}\,\text{ from}\,\text{ each}\,\text{ list}\, \\ 5& \quad H\,=\,\text{empty}\,\text{min-heap} \\ 6& \quad \textbf{for }\,i\,=\,1\textbf{ to }\,k \\ 7& \quad \qquad \textbf{if }\,lists[i]\,\text{is}\textbf{ not }\,\text{empty} \\ 8& \quad \qquad \qquad \textsc{Min-Heap-Insert}(H, \, (lists[i][1], \, i, \, 1))\quad \textbf{/\!/} \text{ (value,}\,\text{ listIndex,}\,\text{ index)}\, \\ 9& \quad \\ 10& \quad \textbf{/\!/} \text{ Extract}\,\text{ minimum}\,\text{ and}\,\text{ refill}\,\text{ from}\,\text{ same}\,\text{ list}\, \\ 11& \quad \textbf{for }\,j\,=\,1\textbf{ to }\,n \\ 12& \quad \qquad \textbf{if }\,H\,\text{is}\,\text{empty} \\ 13& \quad \qquad \qquad \textbf{error }\text{\textquotedblleft lists contained fewer than n elements\textquotedblright} \\ 14& \quad \qquad (v, \, idx, \, pos)\,=\,\textsc{Heap-Extract-Min}(H) \\ 15& \quad \qquad result[j]\,=\,v \\ 16& \quad \qquad next\,=\,pos\,+\,1 \\ 17& \quad \qquad \textbf{if }\,next\,\leq\,lists[idx]\,.length \\ 18& \quad \qquad \qquad \textsc{Min-Heap-Insert}(H, \, (lists[idx][next], \, idx, \, next)) \\ 19& \quad \\ 20& \quad \textbf{return }\,result \\ \end{aligned}$$

How It Works

Initialization: We create a min-heap and insert the first element from each of the $k$ lists. Each heap entry stores not just the value, but also which list it came from and its position in that list. This takes $O(k \lg k)$ time ($k$ insertions, each costing $O(\lg k)$).

Main loop: We repeat $n$ times:

Extract the minimum element from the heap (this is the next element in sorted order)
Add it to the result array
If the list that element came from has more elements, insert the next element from that list into the heap

Each extraction takes $O(\lg k)$ time, and each insertion takes $O(\lg k)$ time. With $n$ iterations, the total time is $O(n \lg k)$.

Example

Consider merging three lists:

List 1: $\langle 1, 4, 7 \rangle$
List 2: $\langle 2, 5, 8 \rangle$
List 3: $\langle 3, 6, 9 \rangle$

Initial heap: $\{(1, 1, 1), (2, 2, 1), (3, 3, 1)\}$

Step 1: Extract min = (1, 1, 1). Output: [1]. Insert (4, 1, 2). Heap: $\{(2, 2, 1), (3, 3, 1), (4, 1, 2)\}$

Step 2: Extract min = (2, 2, 1). Output: [1, 2]. Insert (5, 2, 2). Heap: $\{(3, 3, 1), (4, 1, 2), (5, 2, 2)\}$

Step 3: Extract min = (3, 3, 1). Output: [1, 2, 3]. Insert (6, 3, 2). Heap: $\{(4, 1, 2), (5, 2, 2), (6, 3, 2)\}$

Continue until all elements are processed, yielding [1, 2, 3, 4, 5, 6, 7, 8, 9].

Time Complexity Analysis

Building the initial heap: $O(k \lg k)$ (can be optimized to $O(k)$ using $\textsc{Build-Min-Heap}$)

Main loop: $n$ iterations, each performing:

One $\textsc{Heap-Extract-Min}$: $O(\lg k)$
At most one $\textsc{Min-Heap-Insert}$: $O(\lg k)$

Total for main loop: $O(n \lg k)$

Overall time complexity: $O(n \lg k)$

Space Complexity

The algorithm uses $O(k)$ space for the heap (at most $k$ elements) plus $O(n)$ space for the output array. If we count only auxiliary space (not counting input and output), it’s $O(k)$.