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

## Java

Output:

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

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

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 🙂

Get great deals at Amazon