2 External-Memory Sorting

This lecture will cover sorting in the cache-oblivious world. Sorting seems like an unusual topic for a data structures course, but as we will see, the results of our discussion of cache-oblivious sorting will lead to our development of cache-oblivious priority queues. We first review external-memory sorting before moving on to cache-oblivious sorting, priority queues, and Funnel Heaps. 1.1 Notation This lecture uses capital letters in our analysis. We choose this notation because some papers use the notation n = N M B and m = B, where N is the number of elements, M is the size of the cache, and B is the block size. This notation is confusing so we will avoid it