I have received a homework that requires me to Merge K sorted lists having a total of N elements into a single sorted list efficiently. The methods that I have stumbled upon are to use a Min-heap to sort the elements from the K lists or use a Divide and Conquer approach(pair-wise merging). The comments in this thread tells that the Divide and Conquer approach takes Time complexity of O(NK), whereas the Min-heap one takes O(N log K) and both have the same space complexity. I also visited many other threads, but i can't get a clear picture.
Doubts & Questions:
That thread is about an K
-way merge. Which is that you look at the first value of all K
lists, then take one element from one list and repeat.
It is time O(n K)
because for each of n
elements you're looking for the min of K
lists.
Divide and merge takes O(n)
for one set of merges, which cuts the number of lists in half. So after log(K)
merges you're done in time O(n log(K))
.
A min-heap is like the K
-way merge except that it only takes time O(1)
to find the smallest element and O(log(K))
to get it out. So it takes time O(n log(K))
.
A min-heap is an implementation of a priority queue, so it is the same.
All of these methods take the same space, O(n)
.
Good luck coding whichever one you choose!