M/B-Way Mergesort

You’ve seen many useful and interesting things in this chapter, and now we’re going to put them all together. That’s right—it’s time to learn about the external-memory Mergesort algorithm of choice. It’s called M/B-Way Mergesort, and you’ll see soon where this algorithm gets its moniker.

Let’s set the stage. We’re back in a world where our data does not fit in RAM, so we need an external-memory approach for executing Mergesort.

Say that we have a list of 64 data elements, and that our computer has a block size of 4 and a RAM size of 16. We’ve seen this scenario before, and our previous approach, which we called Second-Attempt Mergesort, worked like this:

We had three phases, each of which performed 16 I/Os. This yielded 48 I/Os in total. However, with M/B-Way Mergesort, we can accomplish Mergesort in two phases. Each phase will also take 16 I/Os, but because there are only two phases, we’ll get a total of 32 I/Os.

Here’s how M/B-Way Mergesort works.

The first phase is identical to Second-Attempt Mergesort, in that we begin by creating 4 M-sized sublists:

However, instead of merging these M-sized lists two by two as we did in Second-Attempt Mergesort, we’ll now do something different. Ready for it?

The next step is that we use the Top-Grade Merge algorithm to merge all 4 sublists into our final array. Here’s an overview of what this looks like:

With this approach, we got the job done in just two phases! The first phase spent 16 I/Os loading all the elements and creating the M-sized lists. And the second phase spent another 16 I/Os moving all the elements into the heap. So, in two phases and 32 I/Os, M/B-Way Mergesort shaved off a lot of time.

With that overview taken care of, let’s dig a bit further into the details.

In our context of external-memory sorting, we have to tweak Top-Grade Merge slightly. When I presented Top-Grade Merge earlier, it was as an internal-memory algorithm. In our scenario, though, there’s a slight hurdle.

That is, we’re trying to use Top-Grade Merge to merge 4 lists that each contain 16 values, which means that we’re merging a total of 64 values at once. But if M=16, this means that RAM itself can only hold a max of 16 values at once. So, how can we merge 64 values at the same time?

The answer, though, is that we don’t need to have all 64 values in RAM at once to perform Top-Grade Merge. Instead, we can use a technique that may be familiar to you now—we simply load one block from each list into RAM at once:

Here, we start by loading one block (of size 4) from each of the 16-element M-sized sublists into main memory. We then perform internal Top-Grade Merge on those four blocks, which are essentially four lists. As we exhaust each block, we pull the next block from its associated 16-element sublist. Note that when this diagram shows the four blocks in main memory, it’s a snapshot in time. Eventually, all 64 elements from our original list have to pass through main memory. However, at a given moment in time, there are up to 4 blocks (totaling 16 elements) in main memory.

Just to be super clear: when the diagram shows the 4 blocks of 16 values being inserted into the heap, we’re not inserting all 16 values at once. Again, we’re performing Top-Grade Merge, which means that we’re only inserting one value from each block into the heap, and the heap will hold no more than 4 values at once. The diagram shows the process from a high level.

Now, the heap has to live in main memory, too. In truth, we need our RAM to be large enough to accommodate the blocks and the heap. The diagram doesn’t depict the fact that the heap also lives in main memory, but keep in mind that this will need to be the case.

In short, we merge K sorted lists by merging K sorted blocks. Once we’ve exhausted a particular block, we load the next block from the list where that block came from. At the end of the day, the result is the same as merging K sorted lists.

Now, while this is all very awesome, there’s one last hiccup to deal with.

What’s M/B All About?

At first glance, it may seem that M/B-Way Mergesort will always get the job done in two phases. However, this isn’t the case.

To demonstrate, let’s change up our scenario so that N=256. Assuming that the other variables remain the same (M=16 and B=4), our first phase will produce 16 sorted M-sized sublists:

These M-sized sublists are now back living in external memory once again.

For the next phase, we’d attempt to use Top-Grade Merge just as we’ve done before, but there’s a little catch.

As I’ve explained in the previous section, to perform Top-Grade Merge, we need to load one block from each and every sublist. And this is where we hit a wall. That is, in our scenario, K is 16, meaning that we have 16 sublists. As such, this would require loading 16 blocks. But because B=4, this means that loading 16 blocks means loading 64 values in total. But if M=16, we don’t have room for all 16 blocks; we only have room for 16 elements! In our scenario, RAM can only hold a maximum of 4 blocks.

So, here’s what we do. We don’t perform Top-Grade Merge on all 16 sublists at once. Instead, we merge 4 sublists at a time:

The reason why we choose to merge specifically 4 sublists at once is because RAM can hold a max of 4 blocks at once. Here, we load one block from each of the sublists into main memory. This fits perfectly into our main memory of size 16, as each of the 4 blocks contains 4 data elements, totaling 16 elements.

We then perform the same algorithm as before, which gives us a sorted sublist of 64 elements. This is the oval at the bottom of the diagram.

We’re not done with the algorithm yet, but let me highlight an important takeaway: the greatest number of sublists we can merge at once is identical to the maximum number of blocks that RAM can hold at once.

And what is that number? Well, in our scenario, it was 4, and this is because M=16 and B=4. In other words, the greatest number of blocks that RAM can hold at once is:

And because M/B is the greatest number of blocks that can fit in RAM, M/B is also the greatest number of sublists that we can merge at once.

And that’s where the algorithm of M/B-Way Mergesort gets its name. In M/B-Way Mergesort, we execute a number of phases in which we merge a certain number of sublists at once. And how many sublists do we merge at once? The answer is: M/B.

Let’s walk through the rest of M/B-Way Mergesort. In our current example, we merged the first M/B (4) lists to create a new sublist of size 64. We then proceed to do the same with the other groups of M/B sublists:

This gives us 4 sublists of size 64 each. We’re now ready for the next phase.

Once again, we will use our Top-Grade Merge algorithm to merge these 4 sublists together. And once again, we can only merge M/B sublists at once. Luckily, at this point, we only have M/B sublists to merge, so we can merge them all at once as shown in the .

With this algorithm, we were able to merge the entire list of 256 items in three phases.

As we increase the total number of values (N), the number of phases will increase. However, M/B-Way Mergesort will nonetheless remain the most efficient way to sort the values, no matter how many phases there are. Any other approach would take a greater number of I/Os.

Big O of M/B-Way Mergesort

Now that we’re pros in juggling the variables N, M, B, and K, let’s see if we can figure out how to articulate the Big O of M/B-Way Mergesort. Fortunately, we’ve already done a lot of the heavy lifting when we analyzed the Big O of Second-Attempt Mergesort. We’ve already figured out that the formula for calculating the number of I/Os in Second-Attempt Mergesort is:

We’ve also already figured out that the “number of I/Os per phase” is N/B. Again, this is because in each phase we need to load all N elements, and it takes N/B blocks to do so.

This leaves us to figure out the “number of phases.” As we did with our analysis of Second-Attempt Mergesort, let’s skip the first phase for now.

The second phase starts with M-sized lists. As with Second-Attempt Mergesort, the number of M-sized lists we begin with is N/M. That is, if we divide N into M-sized lists, we’ll have N/M such lists.

Now, in Second-Attempt Mergesort, each phase cuts the number of sublists in half. Based on this, we described the number of phases as log₂ N/M. That is, each phase divides the sublists by 2 until we create one complete list.

In M/B-Way Mergesort, though, each phase divides the number of sublists by more than 2. In our prior scenario, each phase divided the number of sublists by 4.

Now, we’ve seen that this number 4 was computed based on M/B; the maximum number of lists we can merge at once is M/B. And so, each phase consolidates M/B sublists at once. In our example, 16 sublists became 4 sublists, and 4 sublists became 1. Given that each phase divides N/M (M-sized) lists by M/B, we’d say that the total number of phases is log_M/B N/M. In other words, we start off with N/M lists, and we keep dividing that number of lists by M/B until we get one final sorted list.

So, when we multiply this “number of phases,” which we’ve said is log_M/B N/M, by the “number of I/Os per phase,” which is N/B, we get a final Big O of:

O(N/B log_M/B N/M).

If that doesn’t look like gobbledygook, I don’t know what does. However, this Big O Notation is useful because we can now plug in any scenario to figure out approximately how many I/Os will occur.

Let me show one quick example, specifically focusing on the improvement of M/B-Way Mergesort over Second-Attempt Mergesort. Again, the Big O of each is:

Second-Attempt Mergesort: O(N/B log₂ N/M)

M/B-Way Mergesort: O(N/B log_M/B N/M)

They’re almost the same, except that Second-Attempt Mergesort has a logarithm base of 2, while M/B-Way Mergesort has a logarithm base of M/B.

Now, let’s dream up a scenario where we have 100,000 data elements, a RAM size of 1,000, and a block size of 100. In other words, N=100,000, M=1,000, and B=100.

If we plug this into Second-Attempt Mergesort’s Big O, we get:

With M/B-Way Mergesort, on the other hand, we compute:

That’s some pretty significant time savings right there.

Once again, pure Big O Notation is a bit limiting here. Since Big O technically drops logarithm bases, the Big O of both Second-Attempt Mergesort and M/B-Way Mergesort come out to be O(N/B logN/M). But then we wouldn’t be able to tell that there’s any speed difference between the two algorithms. And so, I’m going a bit on a limb and putting the logarithm bases back in so we can measure the precise advantage of M/B-Way Mergesort.