A Second Attempt at External Mergesort

Let’s work with the same scenario of sorting the integers from 1 to 32. In this scenario, naturally, we’d say that N=32. And let’s also continue using a computer whose block size is 4. In other words, B=4. But let’s now upgrade our computer (for just $99!) so that its main memory has a capacity to hold 16 values. Using our new jargon, we’d say that M=16.

With this upgraded RAM, we can achieve external Mergesort using only 16 I/Os via what I’ll call “Second-Attempt Mergesort.” This algorithm will simply be a bridge between Two-Way External Mergesort and our final algorithm, so I won’t even try to come up with a better name for it.

Second-Attempt Mergesort will take 16 I/Os to sort 32 values, which is faster than Two-Way External Mergesort, which took 24 I/Os. Second-Attempt Mergesort is similar to Two-Way External Mergesort, except that we can skip an entire set of steps.

In Two-Way External Mergesort, we merged every pair of blocks to create sublists of size 8. However, since M=16, we can instead kick off our algorithm by filling up RAM with as many blocks as possible. With M=16 and B=4, this means we can load 4 blocks:

With 16 elements in RAM, we can use internal Mergesort (or any internal sorting algorithm, for that matter) to internally sort all 16 elements. And so, after 4 I/Os, we’ve already sorted half of the original list:

After writing this back to disk, we do the same with the second half of the list as shown in the .

From here on, the rest of the algorithm is the same as Two-Way External Mergesort. That is, we perform another 8 I/Os to merge the list’s two sorted halves together.

Essentially, what we accomplished here is that we skipped over the initial steps of merging 2 blocks at a time. There’s no need to merge only 2 blocks at a time if we can instead fill up RAM with 4 blocks at once and use an internal-memory algorithm to sort all the blocks’ elements.

Let’s use another bird’s-eye view to visualize this new algorithm. Here, we’re using a different, but simpler style of showing the data. Each oval represents a list or sublist of data with a particular size:

The top row shows that the original list is divided into 8 sublists of size 4, which is equal to our block size. These 8 sublists are divided into two rectangles that represent main memory, with each rectangle holding 4 sublists. This is because main memory, whose M=16, can hold a maximum of 4 sublists, which total 16 elements.

Loading these 8 sublists into RAM takes 8 I/Os since the job of an I/O is to load a single block into memory, and each sublist fits perfectly into one block. Each time RAM is filled with its maximum capacity of 4 sublists, it sorts the 4 sublists to create a single sorted sublist of 16 elements, which are depicted by the second row in the diagram. Note that I’ve labeled these lists as being M-sized lists since each list indeed has a size that is equal to M. We’ll talk more about the significance of the term “M-sized lists” soon.

The rest of the algorithm is identical to Two-Way External Mergesort. We take blocks from the two M-sized sublists and merge them together to create a final sorted list of size 32. This takes another 8 I/Os in total since we have to load all the elements again—which take up a total of 8 blocks—when doing the merging. This final merge produces a fully sorted list of size 32, which is seen on the bottom row.

In sum, the entire algorithm executes a grand total of 16 I/Os.

Before going on, I’d like to highlight a major takeaway from Second-Attempt Mergesort. First and foremost, we’ve discovered another general technique for optimizing external-memory algorithms. In the previous chapter, we looked at the trick of packing blocks with as much useful info as possible. Here, we discovered a new trick, which is to fill RAM with as much data as possible, if we can utilize an internal-memory algorithm to process that data. In our context, it’s a waste to use an internal-memory sorting algorithm on only one or two blocks of data at a time. We may as well fill RAM to the brim, and sort all that data in memory all at once.

Don’t Forget to Eat Your Variables

Let’s now gear up to use Big O Notation to describe the speed of Second-Attempt Mergesort. Even though we’ll ditch Second-Attempt Mergesort eventually, this same analysis will be used in computing the Big O of our final algorithm.

The first thing we need to do is figure out how to describe the number of I/Os that take place using our variables, N, M, and B.

Recall that in the previous diagram, I highlighted in the second row that we created sorted sublists of size M. That is, because we filled RAM (whose size is M) completely before internally sorting the values, we ended up producing M-sized sorted sublists. In our example, this meant that each sorted sublist had a size of 16.

With this in mind, we can use our shiny variables to describe how many M-size sublists we will be creating. In our example, N is 32 (there were 32 values), and M is 16 (our RAM can hold 16 values). Because 32/16=2, we created 2 sublists of size M.

We can now state this more generally: the first part of Second-Attempt Mergesort is to create N/M lists of size M. In other words, we used internal sorting to create a number of M-sized sublists. And how many M-sized sublists did we create? We created the same number of lists as whatever N/M computes to.

However, if we change up the scenario so that our initial list has 64 values (that is, N=64), this is what Second-Attempt Mergesort looks like now:

Once again, we begin by creating N/M sorted sublists of size M. In this case, this comes out to be 4 sorted sublists of size 16. We then merge each pair of sublists to create 2 sublists of size 32. Finally, we merge those 2 sublists to create a fully sorted list of 64 values.

Big O of Second-Attempt Mergesort

Okay, we’re almost ready to use Big O Notation to describe Second-Attempt Mergesort. This is a little more complex than our usual Big O analysis, but we can get there if we take one step at a time. Just tell yourself that it will be fun.

(If you’re not having fun, that’s okay; you can skip ahead. The Big O isn’t critical to understanding the algorithms of this chapter. It just helps us contrast them all to each other in a quantitative way.)

In our most recent example scenario, we spent 16 I/Os in each phase of the algorithm. This is because each phase deals with 64 values, and it takes 16 blocks (of size 4) to load these 64 values. And so, each phase took 16 I/Os. Now, the algorithm underwent 3 phases, yielding a total of 48 I/Os since 16*3=48. It would be reasonable to generalize this for all scenarios and say:

I’ll refer to this equation as our “Grand Formula.” As you can see, we compute the total number of I/Os by multiplying two factors: the number of I/Os per phase and the number of phases. Since these factors are the key to our Grand Formula, I’ll put them in quotes going forward to give them heightened importance.

So, the next thing we need to figure out is how to use our shiny variables to describe these “number of I/Os per phase” and the “number of phases.” Then, we can plug those variables into the Grand Formula.

Calculating the Number of I/Os Per Phase

Let’s start by using our variables to describe the “number of I/Os per phase.” We know that in the previous example, there were 16 I/Os per phase. This, again, was because each phase had to process 64 data elements, and when we divide these 64 values into blocks of size 4, we get 16 blocks. And as we’ve learned, it takes one I/O to load one block. Refer back to the image to make sure this is clear.

As such, we get:

With our variables, we can generalize this formula with:

Tada! We’ve successfully used our shiny variables to calculate the “number of I/Os per phase.” Let’s plug what we have so far into the Grand Formula.

Again, let’s take it from the top. Our Grand Formula to determine the Big O of Second-Attempt Mergesort was:

Now, we’ve figured out that we can articulate the “number of I/Os per phase” as N/B. Accordingly, we can plug this into the Grand Formula, and come out with:

Our next step is to determine how we can use our variables to articulate the “number of phases.”

Calculating the Number of Phases

Look back again at the diagram . Note that there are three phases. The first phase was spent creating the M-sized sublists, and the subsequent phases each cut the number of sublists in half. To make the following analysis easier, let’s temporarily ignore the first phase and instead start our analysis from the second phase on.

The second phase starts with the M-sized sublists. To our great fortune, we’ve already determined earlier that there are N/M of these sublists.

Now, how many phases will it take to keep halving these N/M sublists until we get down to one single list? Well, that would be log₂ N/M.

With that wrapped up, we can now return to the first phase.

We can treat the first phase as simply an extra phase that we add to log₂ N/M. In other words, because the number of phases from the second phase and onward is log₂ N/M, when we add the first phase, we get (log₂ N/M) + 1. And because the “+ 1” is a constant, Big O ignores it, so we can articulate the number of phases as log₂ N/M.

Now that we’ve calculated the “number of phases,” we can plug that back into the Grand Formula.

As of this moment, here’s what the Grand Formula currently looks like:

Since we’ve determined that the “number of phases” is log₂ N/M, we’ll plug that in, leaving us with:

We did it! We can finally conclude that in Big O, our Second-Attempt Mergesort algorithm has the time complexity of O(N/B * log₂ N/M). In truth, Big O Notation drops the log base, but I’ll leave it in because it’ll allow us to make some important comparisons by the end of the chapter.

Now, I’ll be the first to admit that when I look at the expression O(N/B * log₂ N/M), I have trouble deriving much meaning from it. There are too many variables flying around. However, having this Big O benchmark will turn out to be useful when we contrast it with our final algorithm.

An Even Faster External-Memory Mergesort

I guess the heading spoils the surprise, but guess what? There’s a third algorithm for external-memory Mergesort that is even faster than Second-Attempt Mergesort. In fact, this third algorithm isn’t just faster; it’s way faster. And it’s the algorithm the pros use.

Prepare to have your mind blown.

But not yet. You see, we first need to explore a completely different algorithm. But don’t fret. Although this may seem like another hurdle to jump over, this algorithm is super cool and worth learning about, even if you learned nothing else in this chapter.