Lecture 24: Cache-Oblivious Algorithms - Searching and Sorting

What this lecture covers

This is the final lecture of MIT's Design and Analysis of Algorithms, closing out the two-lecture unit on cache-oblivious algorithms. Demaine first finishes the previous lecture's argument that the least-recently-used (LRU) cache eviction policy is a good approximation of the optimal offline strategy, then applies the external-memory and cache-oblivious models to two classic problems: searching a sorted set and sorting an array.

After watching, you can explain why LRU is within a factor of two of optimal caching, describe how B-trees and the van Emde Boas layout achieve log_B n search time, and derive why block-aware multi-way merge sort beats ordinary merge sort by a factor of B rather than just log B. The lecture ends with a rundown of follow-on MIT algorithms courses, followed by an unrelated frisbee-throwing contest between the two lecturers that has no algorithmic content.

Key ideas

• LRU vs. optimal caching: dividing the access sequence into phases with exactly M/B distinct blocks shows LRU pays at most M/B transfers per phase, while an optimal algorithm restricted to a cache of size M/2 must pay at least half that, giving LRU a 2x approximation ratio.
• Online vs. offline algorithms: LRU is online (it only knows the past); the optimal comparison algorithm is offline (it can see the whole future access sequence), which is why LRU cannot match it exactly.
• Predecessor search in comparison model: ordinary binary search on a sorted array only improves to log n - log B memory transfers, not log_B n, because most probes land in different blocks.
• B-trees: giving each node branching factor around B makes search cost log_B n memory transfers, which is optimal, but the tree must know B in advance.
• Van Emde Boas layout: recursively splitting a balanced binary search tree in the middle level and laying out each resulting triangle contiguously gives a cache-oblivious layout achieving O(log_B n) search without ever knowing B or M.
• External-memory merge sort: standard merge sort is already cache-oblivious and costs (n/B) log(n/M) transfers, an improvement over binary search's log n / log B factor but not yet optimal.
• M/B-way merge sort: splitting into M/B groups instead of two and merging them with parallel scans reaches the sorting bound (n/B) log_{M/B}(n/B), which is optimal but requires knowing both M and B.
• Cache-oblivious sorting (funnel sort): achieving the same optimal bound without knowing M or B is possible under the tall-cache assumption (M >= B^(1+epsilon)), using a divide-and-conquer merge called funnel sort.

Walkthrough

Recap: proving LRU is near-optimal (0:00)

Demaine restates the external-memory model (a two-level cache/disk hierarchy with block size B and cache size M) and its cache-oblivious variant, where the algorithm cannot query B or M and block management happens automatically under an LRU eviction policy. He then proves the theorem from the previous lecture: LRU on a cache of size M costs at most twice what an optimal offline algorithm costs on a cache of size M/2. The proof cuts the access timeline into phases, each containing exactly M/B distinct block IDs. Within a phase, LRU pays at most M/B transfers because every block it touches was accessed more recently than anything outside the phase. The optimal algorithm, restricted to M/2, can have at most half its cache already loaded with useful blocks at the start of a phase, so it must pay for at least half of the M/B distinct blocks — giving the factor-of-two bound.

Predecessor search: binary search vs. B-trees (13:20)

The lecture turns to searching for the predecessor of a query element among n static elements. Storing them sorted and running ordinary binary search seems natural, but because each probe jumps to a different block, the cost only improves to log n - log B (equivalently log(n/B)) transfers, not much better than plain log n. Restructuring the data as a B-tree with branching factor around B fixes this: each node fits in a constant number of blocks, so search costs O(log_B n) transfers, matching the optimal comparison-based bound. The catch is that a B-tree must be built knowing B, so it is not cache-oblivious, though it does support inserts and deletes in the same bound.

The van Emde Boas cache-oblivious layout (20:31)

To get the same log_B n bound without knowing B, Demaine presents a layout (attributed to Harald Prokop's thesis, informally called the van Emde Boas layout) built on an ordinary balanced binary search tree. The tree is recursively cut at its middle level, splitting it into a top triangle and roughly sqrt(n) bottom triangles, each laid out recursively and stored as a contiguous block of memory. The analysis shows that once the recursion produces triangles with at most B nodes, each triangle occupies at most two memory blocks, and a root-to-node search path only pays for entering a new triangle, not for movement within one. Bounding the height of these triangles between (log B)/2 and log B gives a search cost within a small constant factor of the optimal log_B n, achieved without the algorithm ever learning B or M.

External-memory and multi-way merge sort (37:53)

Moving to sorting, Demaine notes that inserting n elements one at a time into a B-tree costs n log_B n, which is far from optimal. Ordinary merge sort, which is naturally cache-oblivious, does better: dividing in half is free, each recursive call operates on a contiguous sub-array, and the merge step is three interleaved sequential scans costing n/B transfers. Solving the resulting recurrence with a recursion tree gives (n/B) log(n/M) transfers — a large improvement over binary search's log n / log B because it divides by B rather than log B.

The optimal sorting bound and cache-oblivious sorting (48:12)

To do even better, the lecture generalizes to an M/B-way merge sort: splitting the array into M/B chunks (the largest number of parallel scans the cache can support) rather than two. This changes only the number of recursion levels, giving the sorting bound (n/B) log_{M/B}(n/B), which is optimal and matches the corresponding external-memory lower bound. Achieving this same bound cache-obliviously — without knowing M or B — requires an extra condition called the tall-cache assumption (M >= B^(1+epsilon)) and a divide-and-conquer merge technique called funnel sort, which Demaine describes only in outline since a full treatment would take another lecture.

Priority queues and course recommendations (59:13)

Demaine closes the technical content by noting that cache-oblivious priority queues generalize the sorting result: insert and delete-min each cost (1/B) log_{M/B}(n/B) amortized transfers, so performing n inserts followed by n delete-mins reproduces the sorting bound. He then surveys follow-on MIT courses, including 6.854 (Advanced Algorithms), 6.851 (Advanced Data Structures), 6.850 (Computational Geometry), 6.849 (Geometric Folding Algorithms), 6.852 (Distributed Algorithms), 6.853 (Algorithmic Game Theory), 6.855 (Network Optimization), 6.856 (Randomized Algorithms), 6.857/6.875 (Applied/Theoretical Cryptography), 6.816 (Multicore Programming), and the theory-of-computation sequence 6.045/6.840. The lecture ends with a lighthearted, non-technical frisbee-throwing contest between the two course lecturers that has no course content.

Before you watch

• Review the external-memory and cache-oblivious models and the LRU-vs-optimal setup from the previous lecture in this course, since this lecture opens by completing that proof.
• Be comfortable with merge sort's standard recurrence and with solving recurrences using recursion trees.
• Know what a B-tree is; the lecture assumes you have seen the basic structure before introducing the branching-factor argument.

Check your understanding

1. Why does ordinary binary search on a sorted array fail to achieve O(log_B n) memory transfers, even though it is a divide-and-conquer algorithm?
2. In the LRU-vs-optimal proof, why does restricting the optimal algorithm to a cache of size M/2 bound how much "carryover" it can exploit between phases?
3. Explain why each triangle in the van Emde Boas layout occupies at most two memory blocks once its size drops to B or fewer nodes.
4. Why does M/B-way merge sort achieve a division by B in its running time while ordinary binary merge sort only divides by log B?
5. What extra assumption is needed to achieve optimal sorting performance cache-obliviously, and what does that assumption mean about the shape of the cache?