A First Attempt: Two-Way External Mergesort

Over the course of this chapter, we’ll make a few attempts at designing an effective Mergesort algorithm for external data. We’ll start with a basic approach and optimize it for speed as we move along. By building up the concepts one layer at a time in this way, you’ll have a much stronger appreciation and grasp of what will be our final algorithm.

Until this point, we’ve been using examples where the computer’s memory blocks are the same size as RAM itself. In other words, RAM was just large enough to hold a single block. Indeed, we never cared about the RAM size in the first place. As long as it was large enough to hold a block, everything worked out nicely. However, having a computer that can only store one block in RAM will pose a significant hurdle for external-memory Mergesort.

In the following example, let’s say that our block size is 4, and that main memory can only hold one block. Let’s also say that we had to sort the following list of 8 integers from the filesystem:

Okay, so the first thing we’d do is load our first block into memory:

Once we have some data in memory, we can use internal Mergesort to sort the data within RAM.

With this data sorted, we can now spend another I/O to write these sorted values back to the filesystem:

Next, we’ll do the same thing with the second half of the list. That is, we spend another two I/Os to load the second block and write those sorted values back to the file. And so, we now have a list whose two halves are sorted, but the entire list is not yet properly sorted:

This is the perfect setup for Mergesort, as all we need to do is merge these two halves together.

But here’s the catch. To merge the two halves, we have to be able to access both halves at the same time. However, each half is contained within one block, and if RAM can only hold one block at a time, we have no way to access both halves simultaneously! If our RAM can hold no more than a single block, we’re kind of stuck.

The good news is that in real life, a computer’s RAM is much larger than the block size. And so, main memory has the capacity to hold many blocks.

In our example, we can solve everything by increasing our example computer’s RAM to be able to store up to 8 values. This is equivalent to 2 blocks, which means that we can now proceed with external Mergesort.

To make things fun, let’s change up our scenario so that we’ll be sorting 32 values. For example, here’s a list of the integers from 1 through 32 in random order:

This list exists on the filesystem, and again, our goal is to sort the list. Let’s start by loading the first two blocks into memory, which takes two I/Os:

Next up, we can sort each block independently. We can do this with internal Mergesort:

We then merge the two blocks:

Technically, this merge makes a copy of the original data, so our RAM might have to contain up to 4 blocks. Alternatively, when we merge the data, we can insert the data right back into the file instead of storing the sorted data in RAM.

In any case, we spend another two I/Os writing this sorted sublist back to disk.

Let’s now skip ahead and say that we did this for the entire list, creating 4 ordered sublists, with each sublist containing 8 elements:

We now want to merge the sublists together to put the entire list in order. So our next immediate goal is to merge Sublist #1 with Sublist #2.

At first glance, though, it may seem impossible to merge sublists of 8 values if our RAM itself can only hold 8 values. How do we get both sublists into memory?

Well, this is how. Ready for a trick?

We load the first block of each sublist into memory. We begin by merging most of the values of the two blocks:

Here, we’ve merged the entire first block with the 11 and 12 from the second block, but we’ve paused there. This is because we cannot yet merge the 20 and 22 from the second block, since it’s possible that the remainder of Sublist #1 still contains values that are less than 20 or 22. In fact, Sublist #1 contains a 21, and if we merged in the 20 and 22 now, the 21 would wind up being after the 22, which is just plain wrong.

What we do instead is that as soon as we complete merging values from one entire block, we load in the next block from the sublist that the completed block came from. In our example, because we’ve already merged all the values from one whole block, namely, the 5, 14, 16, and 19, and because this block came from Sublist #1, we now load the next block from Sublist #1:

In this image, we load in the second block from Sublist #1, which is the block containing the values 21, 25, 29, and 32. (I grayed out the 11 and 12 to indicate that they’ve already been merged previously.) We merge the 20 from the second block, the 21 from the first block, and then the 22 from the second block. At this point, we’ve exhausted the second block. Because this block came from Sublist #2, we now load in the next block from Sublist #2 and merge all the remaining values from Sublist #1 and Sublist #2:

We’ve now successfully merged Sublists #1 and #2, which is pretty exciting. But do keep in mind that this only represents half of our original list, which contains 4 sublists. As such, we then repeat these same steps for Sublists #3 and #4. Once this is done, we are left with two sorted halves of our original list, with each half containing 16 elements.

This brings us to the final phase of our algorithm, which is to merge the two 16-element lists together. Indeed, we can accomplish this the same way we merged the 8-element sublists together, which is to load one block from each 16-element list into memory and merge those blocks. As soon as we exhaust one block, we simply load the next block from that list.

It turns out that to execute this external-memory Mergesort algorithm, we require a RAM that can hold 2 blocks of data at once. Again, this is because we’re continuously merging 2 sublists and using one block from each sublist to do so.

Because this algorithm’s modus operandi is to keep merging 2 sublists at once, some call this algorithm Two-Way External Mergesort.

A Bird’s-Eye View of Two-Way External Mergesort

Let’s visualize Two-Way External Mergesort from a bird’s-eye view:

The top row of this image depicts the initial merges that occur. To merge a block, we must load it into memory with an I/O, so it takes a total of 8 I/Os to conduct all the initial merges. (For now, we’re not counting the I/Os of writing back to disk.)

Each of these merges produced a sublist of 8 elements, which can be seen on the second row from the top.

This second row shows how we then merged each pair of sublists together to get larger sublists of 16 elements. This takes another 8 I/Os, since we must load 8 blocks (of size 4) to load all 32 elements into RAM. This produces two larger sublists that each contain 16 elements.

The third row indicates that we spend yet another 8 I/Os to merge the two 16-element sublists. This finally produces the sorted list we’ve yearned for. At the end of the day, it took us a grand total of 24 I/Os of loading data into main memory.

It turns out that even with our computer’s constraints of having a block size of 4 and a RAM size of 8, Two-Way External Mergesort is a fine algorithm indeed. Had we used external-memory Selection Sort on the same 32 data elements, it would have taken us 256 I/Os!

However, with a little more RAM, we can design even faster versions of external-memory Mergesort.