subroutine calls.) Most cache-oblivious algorithms rely on a divide-and-conquer approach. They reduce the problem, so that it eventually fits in cache no matter how small the cache is, and end the recursion at some small size determined by the function-call overhead and similar cache-unrelated optimizations, and then use some cache-efficient access pattern to merge the results of these small, solved problems. Like external sorting in the external memory model, cache-oblivious sorting is possible in two variants: funnelsort, which resembles mergesort, and cache-oblivious distribution sort, which resembles quicksort. Like their external memory counterparts, both achieve a running time of , which matches a lower bound and is thus asymptotically optimal. Practicality An empirical comparison of 2 RAM-based, 1 cache-aware, and 2 cache-oblivious algorithms implementing priority queues found that: Cache-oblivious algorithms performed worse than RAM-based and cache-aware algorithms when data fits into main memory. The cache-aware algorithm did not seem significantly more complex to implement than the cache-oblivious algorithms, and offered the best performance in all cases tested in the study. Cache oblivious algorithms outperformed RAM-based algorithms when data size exceeded the size of main memory. Another study compared hash tables (as RAM-based or cache-unaware), B-trees (as cache-aware), and a cache-oblivious data structure referred to as a "Bender set". For both execution time and memory usage, the hash table was best, followed by the B-tree, with the Bender set the worst in all cases. The memory usage for all tests did not exceed main memory. The hash tables were described as easy to implement, while the Bender set "required a greater amount of effort to implement correctly". See also Cache-oblivious distribution sort External memory algorithm Funnelsort References Models of computation Cache (computing) Analysis of algorithms