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 ]


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.


Download   Run Code


Download   Run Code


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

The 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.

1 Star2 Stars3 Stars4 Stars5 Stars (3 votes, average: 5.00 out of 5)


Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂

Leave a Reply

newest oldest most voted
Notify of

complex problem, tiny code 🙂


I have been following your code-blogs for quite a while, and it’s amazing how clean and easy to understand the codes are. Thank you 🙂