Algorithms and Data Structures for Massive Datasets

11 External memory sorting

This chapter covers

• Understanding the importance of efficient sorting on disk
• Revising the two most classical in-RAM sorting algorithms: merge-sort and quick-sort
• Learning how external memory merge-sort works
• Understanding how external memory quick-sort works
• Understanding the relationship between searching and sorting in internal versus external memory

In the previous chapter, we learned about different ways to design indices in databases. Indices embody the fundamental problem of searching in computer science. Another fundamental problem that crops up in databases—and pretty much everywhere else—is sorting. Just think of how many times you’ve used the function sort() in your code to order a set of data.

Aside from ...