listalgorithmsortingmergen-way-merge

Merging K Sorted Lists: Efficiency


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:

  1. Many other sites told that both the Divide & Conquer and Min-Heap approach have a Time complexity of O(N log K). Is it true or False?
  2. Is the Space complexity of both the approaches same? If not, how do they differ?
  3. Why if the Min-heap approach better than Divide & Conquer for lists of varying length?
  4. I also found that you can use a Priority Queue to solve the problem. How does it compare to these?

Solution

  • 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!