Stefan Edelkamp

QuickMergesort: Practically Efficient Constant-Factor Optimal Sorting

2018 · arXiv (Cornell University)

We consider the fundamental problem of internally sorting a sequence of $n$ elements. In its best theoretical setting QuickMergesort, a combination Quicksort with Mergesort with a Median-of-$\sqrt{n}$ pivot selection, requires at most $n \log n …