AlgoScope

Merge K Sorted Lists

Keep the current heads in a min-heap so the global smallest is always one pop away.

Linked list algorithms, algorithm, intermediate
Take 1 from list a.16825349headtailpqr
Take 1 from list a.16825349headtailpqr

Merging Sorted Lists: Three lists through a heap

Decision, step 2 of 10

Heads: 1 in a, 2 in b, 3 in c. The smallest is 1 from a, so it is unhooked from its list and linked after nothing: it becomes the merged head.

How merging sorted lists works

Cost

Best
O(N log k)
Average
O(N log k)
Worst
O(N log k)
Space
O(k)

N total nodes across k lists.

Taught by the same lesson

Merging Sorted Lists covers these too, in the same run.