Merge K Sorted List

An often seen interview question is the merge of K-Sorted list. The question goes like this:

The simplest but not trivial case for this questions is when k = 2. The algorithm to merge 2 sorted list is relatively straightforward. Use two pointers for each list to remember where the unmerged part starts. Insert the smallest value into the merged list and move the pointer to the next position. When either one of list finished, add the rest of the other list into the final merged list. See below for code example in Python.

This is a straightforward solution if you start approaching this problem from the problem of merge-2-sorted-list. Merge 2 sorted list at a time until you got one single merged list. See the below for code example in Python.

Using heap can help here. The most rudimentary way is to push everything onto a heap and then pop everything out from the heap which will be in order. See below for a code example:

The time complexity of this algorithm is O(klog(nk)). Upon a careful analysis, we notice that this algorithm doesn’t use the fact that each list is sorted. In other words, we just lump everything together into a heap disregarding how they are originally organized.

In fact, the above algorithm is essentially the mergesort algorithm. Inspired by this insight, we can further simplify the above code as:

Wait a minute - wouldn’t any other sorting algorithm also work here? Of course! So the above code could be:

Note that if the question asks you merge linked list, then ‘any other sorting’ algorithm might not work because some of them require random memory access.

Time complexity of the algorithms introduced in this section is O(nklog(nk)). This become obvious if we understand that these algorithms just put every together and re-sort them and time complexity of common comparison sorting algorithms is O(Nlog(N)) .

Is the time complexity here (O(nklog(nk))) better than the time complexity of the algorithm in Method 1( O(nk^2) )? It depends because we have two scaling factors here. If k is the one that scales to very large number (there are many many lists to merge), then just put everything together and resort them is more efficient than merge all lists one by one. If n is the one that scales to very large number (each list has many many elements), then merge the lists one by one is more efficient.

Well, heap can definitely help but we need to use it in a more careful way than in Method 2 and utilize the fact that all input lists have been sorted.

The purpose of using a heap is to efficiently track the smallest number. Since all lists are sorted, we know that the head of each list is already the smallest in that list, so why do we need to add more elements into the heap if we already have the head of each list in the heap? The following algorithm uses heap to track only the head element of each lists and once a head of a list is popped out from the heap, we move the head of the list to the next and add the new head into the heap.

The heap elements need to remember where each element come from, i.e. list index and the position in the list.

Since heap size has been reduced to k, time complexity becomes O(nklog(k)).

The time complexity of this algorithm is also O(nklog(k)). To see why, at each recursion we have these number of pairs of lists to merge:

And the number of comparison is done at each recursion is:

Multiply at each recursion and add all we get O(nklog(k)).

We started with straightforward and intuitive methods (method 1 and 2) and improved on them. The best we can do in time complexity is O(nklog(k)).

Related posts:

FinTech is already disrupting the world of finance at a rapid rate, and it is only going to become more and more entwined into the global ecosystem. Many companies and financial institutions have…

This article continues to automate the container certification procedure using the different CI tools. In this tutorial, we will leverage GitHub Actions to automate the Red Hat Container…

The advantage of having your country on this list is enormous for you as an individual. I will state some of the benefits in the concluding section of this article. According to Chinanalysis (2021)…