SquareSort: a cache-oblivious sorting algorithm
<|reference_start|>SquareSort: a cache-oblivious sorting algorithm: In this paper we consider sorting in the cache-oblivious model of Frigo, Leiserson, Prokop, and Ramachandran (1999). We introduce a new simple sorting algorithm in that model which has asymptotically optimal IO complexity $O(\frac{n}{B} \log_{M/B} n)$, where $n$ is the instance size, $M$ size of the cache and $B$ size of a memory block. This is the same as the complexity of the best known cache-oblivious sorting algorithm FunnelSort.<|reference_end|>
@article{koucký2024squaresort:,
    title={SquareSort: a cache-oblivious sorting algorithm},
    author={Michal Kouck'y and Josef Matv{e}jka},
    journal={arXiv preprint arXiv:2407.14801},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.14801},
    primaryClass={cs.DS}
}