Adaptive Shivers Sort: An Alternative Sorting Algorithm

Abstract

We present one stable mergesort algorithm, called \Adaptive Shivers Sort, that exploits the existence of monotonic runs for sorting efficiently partially sorted data. We also prove that, although this algorithm is simple to implement, its computational cost, in number of comparisons performed, is optimal up to a small additive linear term.

Full version of the article published in the proceedings of the 31th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2020). 39 pages