Wrapping Up

You’re walking away from this chapter with a number of important tools under your belt. First, you know how to wield M/B-Way Mergesort, which is the fastest approach for using Mergesort on external memory. Second, you can now use the Top-Grade Merge algorithm to merge K sorted lists from internal memory in the speediest possible way. And perhaps most important, you now possess the keys for analyzing and optimizing all sorts of external-memory algorithms.

This chapter concludes our ambitious side quest into the world of external-memory algorithms. As I’ve mentioned earlier, this topic can fill an entire volume unto itself. So, it’s time to get back to our “main” storyline: randomization algorithms.

The next chapter will reveal an entirely new class of algorithms that take advantage of randomization. These algorithms, called Monte Carlo algorithms, use randomization to achieve a most shocking trade-off.