Merge M sorted lists of variable length

Given M sorted lists of variable length, print them in sorted order efficiently.


For example,

Input: 4 sorted lists of variable length

[ 10, 20, 30, 40 ]
[ 15, 25, 35 ]
[ 27, 29, 37, 48, 93 ]
[ 32, 33 ]

Output:

10 15 20 25 27 29 30 32 33 35 37 40 48 93


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(Nlog(N)) where N is total number of element present in all lists. Also, this approach do not take advantage of the fact that each list is already sorted.
 

We can easily solve this problem in O(Nlog(M)) 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 20 25 27 29 30 32 33 35 37 40 48 93

Time complexity of above solution is O(Nlog(M)) as heap has size M and we pop and push exactly N times where N is total number of elements. Note that each pop/push operation takes O(log(M)) 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 🙂
 


    

  • AllergicToBitches

    complex problem, tiny code 🙂