Input: m sorted lists having n elements in total
Output: A sorted list containing all elements of the m lists
The problem can be solved in O(n log m) time by using a min heap or a min priority queue (PQ) of size ‘m’ to store the current minimum elements of each list. The algorithm works as follows:
Take a look at C++ implementation with Indexed PQ (see Indexed PQ).
Take a look at C++ implementation with STL heaps.