I/O Efficient Sorting in the Cache Oblivious Model: Quicker than Quick

Dana Jansens

We will introduce the cache oblivious model for algorithm analysis and provide rational behind using the model. An I/O optimal sorting algorithm, called funnelsort, will be presented and analyzed in the cache oblivious model. Experimental results with funnelsort will also be discussed.