External-Memory Sorting

In Volume 1, Chapter 5, I covered the good ol’ simple sorting algorithm, Selection Sort. In a nutshell, Selection Sort performs a linear search through all the values in an array and locates the lowest value. Once you have the lowest value, you swap it with whatever value is at index 0. In the next round, you search all the values from index 1 and on, find the lowest one, and then swap the lowest value with the value at index 1. You then repeat this process for each subsequent index until you reach the end of the array. Selection Sort has a speed of O(N²).

But what would this process look like if the list of values is too large to fit into main memory all at once?

Here’s an example of such a scenario. Suppose that our computer’s block size is 4 integers. We’d like to sort the following list of integers that currently lives in the filesystem:

Before proceeding, I recommend that you try to work out an approach for sorting this data. You can try using a form of Selection Sort or any other sorting algorithm of your choice. I’ll wait.

Okay, ready? Let’s make an attempt at performing external-memory Selection Sort, and we’ll count the number of I/Os along the way, as we discussed back in .

I/O #1: We load the first block into memory. We then do a linear search within this block to find the lowest value, which happens to be 1:

Note that our RAM technically needs to be able to hold more than 4 values since we have to hold the block plus a variable that keeps track of the lowest value. In truth, with Selection Sort we also need to keep track of the index of the lowest value. Let’s assume that our RAM can hold at least 6 values, even though the block size is 4. This foreshadows an important idea we’ll look at soon: a computer’s main memory is generally larger than the block size. But let’s keep things moving.

I/O #2: We load the second block and perform a linear search on it as shown in the first .

This block contains an even lower number than 1—it’s a 0. The 0 is now our new lowest number.

I/O #3: We load the third and final block as shown in the second .

This block’s values are all greater than 0, so 0 remains the lowest value in the list.

The next step of Selection Sort is to swap the 0 with the value that is at the beginning of the list, which happens to be the 9. However, this will take two additional I/Os.

I/O #4: We overwrite the first integer of the list and make it a 0.

This requires an I/O because the act of writing to a file interacts directly with the filesystem. Remember, the “I” of I/O stands for input, while the “O” stands for output. There’s no better example of output than writing to a file. And so, this is a slow operation.

I/O #5: Similarly, we perform another I/O to overwrite the original 0 and replace it with a 9:

This took us a total of 5 I/Os. But lest you think we’re done, we’ve only completed the first round of Selection Sort, as only the 0 is now in its proper place. We still have to sort all the other values!

The next three rounds (to sort the values at indexes 1, 2, and 3) will also each take 5 I/Os.

Technically, the next four rounds after that can use one fewer I/O since we don’t need to load the first four values into memory anymore, as they’ll already be sorted. We’d therefore be able to start the round by loading the block starting at index 4. As we progress through the rounds, the number of I/Os will decrease.

Big O of External-Memory Selection Sort

Let’s now try to describe the speed of external-memory Selection Sort using Big O Notation. We’ll start by analyzing the first round alone.

First, let’s get our variables straight. We’ll use N, as always, to represent the size of our data. In our example, this is 12 since our list contains 12 values. We also have the variable B, which represents the computer’s block size. In our example, this is 4.

Now that our variables are in order, let’s analyze how many I/Os our external-memory Selection Sort takes as it relates to N.

Because N is 12 and B is 4, we have to load 3 blocks to scan the entire list once, as 12 divided by 4 is 3. To put this in terms of N and B, we’d say that we need to perform N/B I/Os to scan the list once.

Now, we also need to perform two final I/Os to swap the values. This means that the first round takes N/B + 2 I/Os. Because Big O ignores constants, though, we reduce this to O(N/B) I/Os. However, keep in mind that this O(N/B) I/Os only describes the time complexity of the first round of Selection Sort. We still have to factor in all the remaining rounds as well.

Let’s pretend for a moment that each and every round must perform N/B I/Os to scan the list, just like the first round. Now, with Selection Sort, we perform as many rounds as there are data elements. It comes out that for each of the N data elements, we perform N/B I/Os. This comes out to be N * N/B I/Os, which we can express as N²/B I/Os.

In the previous section, I pointed out that the number of I/Os decreases as we progress through the rounds. Based on this, we don’t truly perform N²/B I/Os. Technically, we can subtract a certain number of I/Os. However, I explained in Volume 1, Chapter 6 that when we have multiple orders of N, Big O only keeps the highest order. That is, if we have, say, N²+N steps, we’d simply say that the time complexity is O(N²). So in our case, even if we have N²/B - 6N I/Os, we’d drop the “- 6N” and remain with just O(N²/B). In Big O Notation, we’d say that the time complexity of external-memory Selection Sort is O(N²/B) I/Os.

This is most certainly a slow algorithm, but that shouldn’t come as a surprise. After all, Selection Sort, even when performed in memory, is a slow sorting algorithm. As such, we probably don’t want to use Selection Sort as our external-memory sorting algorithm either.

We’ve seen that there are much faster sorting algorithms out there, like Mergesort and Quicksort. Perhaps one of those could work well even when dealing with data in external memory. Let’s try—you guessed it—Mergesort! And so, Mergesort comes back to haunt us once again.