Merge M sorted lists each containing N elements

Given M sorted lists each containing N elements, print them in sorted order efficiently.


For example,

Input: 5 sorted lists of fixed size 4

[ 10, 20, 30, 40 ]
[ 15, 25, 35, 45 ]
[ 27, 29, 37, 48 ]
[ 32, 33, 39, 50 ]
[ 16, 18, 22, 28 ]

Output:

10 15 16 18 20 22 25 27 28 29 30 32 33 35 37 39 40 45 48 50


 
A simple solution would be to create an auxiliary array containing all elements of all lists (order doesn’t matter). Then use a efficient sorting algorithm to sort the array in ascending order and print the elements. The worst case time complexity of this approach will be O(M * N * log(MN)). Also, this approach do not take advantage of the fact that each list is already sorted.

 
We can easily solve this problem in O(M * N * logM) time by using a min-heap. The idea is to construct a min-heap of size M and insert first element of each list into it. Then we pop root element (minimum element) from the heap and insert next element from “same” list as popped element. We repeat this process till the heap is exhausted. Depending upon the requirement, we can either print the popped element or store it in auxiliary array.

 
C++ implementation –
 

Download   Run Code

Output:

10 15 16 18 20 22 25 27 28 29 30 32 33 35 37 39 40 45 48 50

Time complexity of above solution is O(M * N * logM) as heap has size M and we pop and push exactly M*N times. Note that each pop/push operation takes O(logM) time.

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
Sort by:   newest | oldest | most voted
xxxx
Guest
xxxx

we can also merge the lists 2 at a time. We’ll be doing log M merges in total, merging M lists of size N, M/2 lists of size 2N, M/4 lists of size 4N… upto that last merge of 2 lists of size MN/2. Total complexity would be O(MN log M).

wpDiscuz