Multiway Merge : merging m sorted lists

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

2 thoughts on “Multiway Merge : merging m sorted lists

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s