Combine $k$ sorted lists into one

Question

Say I have $k$ sorted lists of the same size $n/k$, and I want to combine them into one sorted array in $O(n\log k)$ time.

The solution I came up with is to recursively halve the lists until you have sections of two lists. Then you combine them by setting a pointer at the start of each one, and placing the smaller element into a new array and incrementing its pointer until you've gone through every element, then return that sorted array.

The combine part does at most $2n$ comparisons, so it's $O(n)$. The recursion depth is $\log_2 k$, since you're halving the remaining lists at each combination. This would give a total of $n\log_2 k$.

Is this a correct implementation and time analysis?

Answer 1

What you describe is a sort of recursive merge which generalizes merge sort, and indeed results in the advertised complexity. The pointer procedure which you are trying to describe is usually just called merge.

Another approach is using a min-heap of size $k$, which stores the current "contenders" for the $k$ smallest elements. It is initialized with the smallest elements of each of the lists, and at each step you pop the smallest element and add it to the merged array, replacing it with the next smallest element in the corresponding list.