Multiway merge is the problem of merging ‘m’ sorted lists into a single sorted list. A 2-way merge, used in merge sort, is a special case of this problem.

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

Advertisements

the time is actually m*n*log(m) since you have to pop the heap m*n times

In the problem statement described in the post, n is taken as the total number of elements across all the lists and so the time complexity turns out to be O(n*log m) as the heap is pushed into and popped n times.

You have assumed n to be the size of each individual list.