Merging K Sorted Lists

In this next section, we’re going to temporarily leave the world of external-memory algorithms and return to some plain old internal-memory algorithms. Eventually, we’ll tie this back into external-memory Mergesort. Okay, here goes.

Whenever I’ve discussed merging lists throughout this book, I’ve always been referring to the idea of merging two lists at once. But let’s say that we have more than two ordered lists, like three, or four, or seventy-six. How would we go about merging them? Again, right now I’m just talking about merging lists in memory. We’re assuming that our RAM can comfortably accommodate all of our lists at the same time.

At first glance, we can apply the classical merging algorithm to as many lists as we’d like. For example, say we have four ordered lists:

Just as with merging two lists, we’d set pointers at the beginning of each list:

We would then compare all the pointers’ values, find the lowest value, and insert it into what will eventually be the merged list. In this case, the 1 from the left-most list gets inserted:

Because we inserted a value from the left-most list, we move the pointer from that list one index to the right.

We then rinse and repeat. So again, we identify the lowest value from all the pointers. In this case, that would be the 2, so we insert it:

And so on and so forth. We repeat this process until all the lists have been merged. I’ll refer to this algorithm as “naïve merging.”

While this approach certainly gets the job done, let’s analyze naïve merging’s time complexity.

In this example, there are a total of 18 values. We spent 18 steps inserting each value into our final, sorted list. But in addition to insertion, we also performed comparisons. That is, before inserting any value, we had to look at 4 different pointer values to find the lowest value—one pointer from each list.

Now, looking at 4 different pointer values takes 4 steps. And we had to perform these 4 comparisons before each and every insertion. So, our total number of comparisons is:

When we add the 18 insertion steps to the 72 comparison steps, we have a grand total of 90 steps.

I also want to highlight a basic, but important idea: the number of pointers is the same as the number of lists. This is because we always maintain one pointer per list.

With this in mind, we can also restate this equation as:

Going forward, we’ll talk in terms of the number of lists rather than the number of pointers; again, these numbers are one and the same.

Big O of Merging Multiple Lists

Let’s now express all of this with Big O Notation.

We can say that N represents the total number of values across all the lists. In the previous example, N=18.

Now, we’ll need another variable to represent the number of lists we’re merging. For this, many computer scientists have decided to use K, which indeed is a nifty letter.

In fact, these same wonderful people also refer to our problem as merging K sorted lists. That is, instead of merging 2 sorted lists, we are merging K different sorted lists. In the previous example, K happened to be 4, but we can also have a scenario where we’re merging 76 sorted lists, in which case K=76.

With our N and K variables in place, we can now express the total number of steps of naïve merging:

In Big O, we drop the “+N” since that’s considered a lower order than NK. And therefore, we’d say that naïve merging has a speed of *O(NK).

Merging K Sorted Lists with Heaps

Now, there’s a second approach we can use to merge K sorted lists. This approach involves the heap data structure, which I covered back in Volume 1, Chapter 16.

Here’s a quick reminder of the points we need to recall about heaps for the sake of our discussion here:

1. Insertion into a heap has a speed of log₂ N.

2. When we pop (in other words, remove) a value from a heap, we always get the lowest value from the heap.

3. Like insertion, popping also has a speed of log₂ N.

In truth, a heap can arbitrarily be set up as either a min-heap, where popping from the heap gives us the lowest value, or as a max-heap, where we get the greatest value. For our purposes here, we’ll use a min-heap, which is why I mentioned earlier that popping from a heap gives us the lowest value.

Now, how can we use a heap to merge multiple lists?

Perhaps the most straightforward thing to do is simply insert all the values from all the lists into the heap. We have N values to insert and each insertion takes log₂ N steps, so completing all the insertions will take N log₂ N time.

We can then pop all the values, one at a time, into our final list. Each pop gives us the lowest value currently in the heap. And so, as we keep popping values, we are effectively creating a perfectly sorted list. Indeed, this is a pretty famous algorithm called Heapsort.

Now, each pop takes log₂ N steps, and because we do it N times, we get a total of N log₂ N pops.

In sum, we have N log₂ N insertions and N log₂ N pops. While this is technically 2(N log₂ N) steps, we drop the constant and have a sweet speed of O(N log₂ N). This algorithm doesn’t care about the number of lists (K) because the same steps would occur no matter how many lists the N values are divided into.

So, is Heapsort’s O(N log₂ N) better than naïve merging, which is O(NK)? Well, it depends on what K is. Say that N is 50 and K is 10. In this case, O(N log₂ N) comes out to be about 300. That is:

By contrast, the O(NK) naïve merging algorithm would take 500 steps since:

In this scenario, where N=50 and K=10, the O(N log₂ N) Heapsort algorithm is faster.

However, in an alternative scenario where N is 50 but K is only 5, we’d find that the O(NK) naïve merging algorithm is faster. In this case, the O(NK) algorithm will take only 250 steps since:

It emerges that the two algorithms are competitive, and which one is faster depends on how many lists there are. However, the top-grade approach I’ll introduce next is faster than either of these algorithms in all cases.

The Top-Grade Way to Merge K Sorted Lists

It turns out there’s a much faster way of merging K sorted lists—faster than either approach we covered so far. This third algorithm doesn’t have a special name that I’m aware of; it’s simply the best way to merge K sorted lists. For the sake of clarity, though, I’ll refer to this new algorithm as “Top-Grade Merge.”

Now, the interesting thing is that Top-Grade Merge is a kind of hybrid of our previous two approaches! It uses a heap, but relies on the following epiphany: we don’t have to throw all the values into the heap at once. The more the heap contains, the slower it is. All we truly need the heap to contain at a given time is one value from each list. But don’t worry; this will all make more sense when we walk through the Top-Grade Merge algorithm, which we’ll do now.

Here’s how the Top-Grade Merge algorithm works:

Step 1: We start with pointers at the beginning of each list. We also insert all these values into our heap:

As you’ll see, the heap will never contain more than 4 values. Also note that in these diagrams, I place the lowest value at the bottom of the heap.

Step 2: Next, we pop from the heap and insert the popped value into what will be our final sorted list. In this case, it’s the 1 that gets popped:

Step 3: Now, here’s the next major rule of the algorithm: we track down which list the popped value came from, and move that list’s pointer to the right. We then place that pointer’s value into the heap:

In this case, the popped value of 1 came from the left-most list, so we move the left-most list’s pointer to the next index. This happens to be the 5, so we add the 5 to the heap.

From here on, we rinse and repeat. This means that next, we’d pop the 2 from the heap and insert it into the final list. Because the 2 came from the second list, we move the second list’s pointer to the right. This points to the 6, which we then insert into the heap. We repeat this entire process until we’ve exhausted all the values from all the lists.

Here’s the gist of why this algorithm is both effective and fast. It’s similar to naïve merging, where we compared the lowest value from each list, picked out the lowest number, and inserted it into the final list. However, whereas in that approach we had to spend K steps comparing the K pointer values, in Top-Grade Merge, we rely on the heap to spit out the lowest of the K values. And the heap can do that much faster than K steps; it can do so in log₂ K time.

Top-Grade Merge is also much faster than Heapsort, in which we simply threw all N values into the heap at once. When we do that, the heap’s operations each take O(log₂ N) time. But in Top-Grade Merge, our heap needs only to contain K values at once. And K is smaller than N since the number of lists will certainly be smaller than the number of total values.

So, the heap’s operations in Top-Grade Merge take log₂ K time, which can be considerably faster than log₂ N time. Therefore, Top-Grade Merge is faster than Heapsort, as the heap in Heapsort takes log₂ N time for each of its operations.

With all this in mind, let’s calculate precisely how many steps take place in Top-Grade Merge.

Big O of Top-Grade Merge

Let’s do the math. With Top-Grade Merge, we ultimately have to insert N values into the heap. We’ve also seen that heap insertion for Top-Grade Merge takes log₂ K steps. Because we spend O(log₂ K) time inserting each of the N values into the heap, this amounts to a total of N * log₂ K steps.

Now, we do also have to execute another N * log₂ K steps in popping the values from the heap. This gives us a grand total of 2(N * log₂ K) steps. But again, since Big O drops the constant of 2, we reduce this back to O(N log₂ K).

And so, Top-Grade Merge has a total time complexity of O(N log₂ K).

Comparing the Three Ways to Merge K Sorted Lists

We now have three different algorithms for merging K sorted lists with three different speeds. To sum it up:

• Naïve merging: O(NK)
• Heapsort: O(N log₂ N)
• Top-Grade Merge: O(N log₂ K)

We’ve already seen that sometimes naïve merging can be faster than heapsort, and in other scenarios, heapsort can be faster than naïve merging. However, Top-Grade Merge is always the fastest of the three. We’ve touched on the reasons for this a bit ago, but here’s a crystal-clear summary.

When we compare Top-Grade Merge with naïve merging, it’s pretty clear that Top-Grade Merge is the winner. This is because log₂ K is always smaller than K itself. And so N * log₂ K is definitely smaller than N*K.

Similarly, Top-Grade Merge is always faster than Heapsort since N * log₂ K is smaller than N log₂ N. This is because K is always smaller than N; the number of lists will certainly be smaller than the number of total values.

Let’s take a look at how this all plays out in an example scenario.

Say that we have 10,000 values across 10 lists with 1,000 values in each list. In other words, N=10,000 and K=10. Here’s how many steps each of the three algorithms would take:

• Naïve merging: 100,000 steps
• Heapsort: 140,000 steps
• Top-Grade Merge: 40,000 steps

As you can see, Top-Grade Merge is the fastest way to merge K sorted lists.

As I stated earlier, the entire discussion of merging K sorted lists has been in the context of merging data in main memory. However, we can now apply a similar idea to give a turbo boost to external-memory Mergesort. Remember that?

Code Implementation: Merge K Sorted Lists

I implemented a Python heap back in Volume 1, Chapter 16. The implementation here is basically the same, except that now we’re using a min-heap instead of a max-heap. (For an explanation of the following code, refer to Volume 1, Chapter 16.) I’ve gone ahead and saved this in a file called heap.py:

Armed with this min-heap, we can now implement the Top-Grade Merge algorithm for merging K sorted lists, as follows:

Let’s break this method down.

We first import the heap module so we can use it in our code. The merge_k_sorted_lists method begins like this, accepting an array of arrays called lists:

The purpose of this method is to take all the arrays within lists and return a single array containing all the values in ascending order. Here, we call that single array sorted_list, which starts out empty at the beginning.

We also set a pointers variable. This will keep track of all the pointers to the different lists. For example, say that we have four lists. Let’s also say that the first list’s pointer is currently at index 3, the second list’s pointer is currently at index 5, the third list’s pointer is currently at index 0, and the fourth list’s pointer is currently at index 2. In this case, the pointers variable will hold the array [3, 5, 0, 2].

Next, we create a heap, which we keep in a variable aptly named heap.

Our method continues by initiating a loop:

We iterate over all the arrays in lists. In this loop, we insert the first value from each list (that is, list[0]) into the heap. However, we don’t insert the value alone. Instead, we wrap the value inside an array that also contains a second item, namely, the identity of the list that the value came from. The identity of the list is represented by its index within the lists variable.

So, if we insert [3, 1] into the heap, that means we’ve inserted the value 3, and indicated that this 3 originated from the second list. Again, the 1 represents the second list because lists contains all the original lists starting at index 0, so lists[1] is the second list.

Because we’ve already inserted the first value from each list into the heap, we can start each list’s pointer at 1 (the second index), so for each list we append a 1 into the pointers array.

Up until now, the method has largely been focused on setting things up. The remainder of the method represents the primary merging algorithm.

The merging algorithm is powered by a loop that runs as long as the heap contains anything. The reason for this is that, as I explained earlier, our merging is complete once the heap has been emptied completely. Here’s the first part of the loop:

We pop the lowest item from the heap and put it in a variable called popped_item. As I explained earlier, this popped_item is not solely the lowest item. Rather, it’s an array whose first value is the lowest item and whose second value is an integer pointing to the list where the lowest item originally came from.

We then append the popped_value to the sorted_list, which puts the popped_value in its proper sorted order.

The loop continues as follows:

We use the integer current_list to point to the original list where the popped_value came from.

If the current_list’s pointer hasn’t yet reached the end of that list, we grab the next_item_from_current_list, which is the value that the pointer of the current_list is pointing to. In other words, we’re grabbing the next item from the current_list.

We then insert the next_item_from_current_list into the heap. Together with this value, we also insert the current_list so we can track which list this value came from. Before concluding our loop, we move the pointer from the current_list to the next index of that list.

Once the loop is done, we return our sorted_list, which is the completely merged list.