World's most popular travel blog for travel bloggers.

Combine $k$ sorted lists into one

, , No Comments
Problem Detail: 

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?

Asked By : MarksCode
Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback