The influence of caches on the performance of sorting

We investigate the effect that caches have on the performance of sorting al gorithms both experimentally and analytically. To address the performance p roblems that high cache miss penalties introduce we restructure mergesort, quicksort, and heapsort in order to improve their cache locality. For all t hree algorithms the improvement in cache performance leads to a reduction i n total execution time. We also investigate the performance of radix sort. Despite the extremely low instruction count incurred by this linear time so rting algorithm, its relatively poor cache performance results in worse ove rall performance than the efficient comparison based sorting algorithms. Fo r each algorithm we provide an analysis that closely predicts the number of cache misses incurred by the algorithm. (C) 1999 Academic Press.