External Merge Sort: Runs and Multi-way Merging

1. The Core Problem: Sorting Data Larger than Memory

When you have a small array of data in C++ or Java, you can simply call a library function like std::sort or Arrays.sort(). These are highly optimized in-memory algorithms, like Introsort or Timsort, that assume all the data is readily accessible in RAM.

But what if you need to sort a 100 GB file with only 1 GB of RAM? You can't load the whole file. This is the domain of external memory algorithms, which are designed to minimize the primary bottleneck: slow disk I/O.

To set the stage, let's watch a brief introduction that explains why we need specialized algorithms for this scenario.

2. The External Merge Sort Algorithm: A Two-Phase Approach

The solution to sorting huge files is a classic "divide and conquer" strategy called External Merge Sort. It breaks the problem into two distinct phases:

1. Phase 1 (The Sort Phase): Read the large file in chunks, where each chunk is small enough to fit into memory. Sort each chunk individually using a fast in-memory algorithm and write the sorted chunk back to a temporary file on disk. Each of these temporary sorted files is called a run.
2. Phase 2 (The Merge Phase): After creating all the runs, merge them into a single, globally sorted file. This is done by simultaneously reading the beginning of each run, repeatedly picking the smallest value among them, and writing it to the final output file.

This diagram provides a high-level visual of the entire process.

Let's walk through a simplified example to see how the data flows.

3. Implementing Phase 1: Creating Sorted Runs

Let's dive into the implementation, which is surprisingly straightforward. Given your background in C++, you'll find the logic very familiar. The goal of this phase is to read the entire input file and write out a set of temporary, sorted files (the runs).

The core logic of Phase 1 can be summarized in this pseudocode:

// Pseudocode for Phase 1: Creating Runs
buffer = allocate_memory(M_bytes);
input_file = open("large_file.dat");
run_count = 0;

while (!input_file.end_of_file()) {
    // 1. Read a chunk of data into the buffer
    bytes_read = input_file.read(buffer, M_bytes);

    // 2. Sort the buffer in-memory
    std::sort(buffer, buffer + bytes_read);

    // 3. Write the sorted buffer to a new temporary run file
    output_run_file = open("run_" + run_count + ".tmp");
    output_run_file.write(buffer, bytes_read);
    output_run_file.close();

    run_count++;
}

At the end of this phase, the single large, unsorted input file has been transformed into N/M smaller, individually sorted run files on disk, where N is the total file size and M is the memory buffer size.

4. Implementing Phase 2: The Multi-Way Merge

Now we have a collection of sorted runs. The next step is to merge them. While we could merge them two at a time (as in the simple video example), this would require multiple passes over the data. A much more efficient method is to perform a k-way merge, where we merge k runs simultaneously.

The key challenge in implementing a k-way merge is this: at each step, how do you efficiently find the smallest element among the current heads of all k runs?

A naive linear scan would take O(k) time for every single element we write to the output. We can do much better by using a min-heap data structure.

The algorithm for the merge phase is as follows:

1. Open all k run files for reading.
2. Create a min-heap (in C++, this is a std::priority_queue with a custom comparator).
3. For each run, read the first element and push it onto the heap. It's helpful to store it as a pair: {value, run_index}.
4. While the heap is not empty:
   a. Pop the minimum element {value, run_index} from the heap.
   b. Write value to the output file.
   c. Read the next element from the run file indicated by run_index.
   d. If that run is not exhausted, push the new element onto the heap.

This approach is highly efficient. The heap always contains exactly k elements (one from each run), and each pop/push operation takes only O(log k) time.

Let's return to the algorithmica.org article to see how this is implemented in C++.

An Advanced Optimization: Replacement Selection

The length of your initial runs is limited by the size of your memory buffer. However, a clever technique called Replacement Selection can often create runs that are, on average, twice the size of your available memory. This reduces the number of initial runs, which in turn can reduce the number of merge passes needed.

This is an advanced topic, but if you're curious about the algorithm, this video provides an excellent explanation.

Conclusion

Congratulations! You've just walked through the design and implementation of one of the most fundamental algorithms in database systems. It's a perfect example of how systems are designed to overcome physical hardware limitations like memory size and disk speed.

Key Takeaways:

• External Merge Sort is a two-phase algorithm for sorting datasets that are too large to fit in RAM.
• Phase 1 (Sort): Create initial sorted runs by sorting memory-sized chunks of the input data and writing them to temporary files.
• Phase 2 (Merge): Perform a k-way merge on the runs. A min-heap (std::priority_queue) is the ideal data structure to efficiently find the next smallest element across all runs.
• The entire algorithm is designed to favor sequential disk I/O (reading and writing large blocks) and to minimize the number of passes over the data.

Preview of the Next Lesson

In this lesson, we focused on the implementation. In the next one, we will formally analyze the I/O cost of external merge sort, calculating the total number of disk reads and writes required. We'll also see how this powerful sorting primitive can be used to implement another relational operator: projection with duplicate elimination (the SELECT DISTINCT clause).