Chapter 8
Wrangling Big Data with M/B-Way Mergesort

The previous chapter introduced the concept of external-memory algorithms and the unique approach for measuring and optimizing their time complexity. Most of the discussion revolved around optimizing external-memory search algorithms. But let’s take this conversation to the next level and talk about how we might design external-memory sorting algorithms.

Consider the following scenario:

We want to sort a list of values. However, we have so much data that we can’t fit all the values in RAM at once. How can we sort them?

In this chapter, you’ll learn the optimal solution for solving this problem. Along the way, you’ll also learn about a useful in-memory algorithm for merging many lists simultaneously—a problem commonly known as merging K sorted lists. And most importantly, you’ll gain further sophistication in analyzing external-memory algorithms and developing ways to optimize their speed.