1 Answers
The cache-oblivious distribution sort is a comparison-based sorting algorithm. It is similar to quicksort, but it is a cache-oblivious algorithm, designed for a setting where the number of elements to sort is too large to fit in a cache where operations are done. In the external memory model, the number of memory transfers it needs to perform a sort of N {\displaystyle N} items on a machine with cache of size Z {\displaystyle Z} and cache lines of length L {\displaystyle L} is O {\displaystyle O} , under the tall cache assumption that Z = Ω {\displaystyle Z=\Omega }. This number of memory transfers has been shown to be asymptotically optimal for comparison sorts. This distribution sort also achieves the asymptotically optimal runtime complexity of Θ {\displaystyle \Theta }.