QuickHeapsort, an efficient mix of classical sorting algorithms (Q1608335)

We present an efficient and practical algorithm for the internal sorting problem. Our algorithm works in-place and, on the average, has a running-time of \(O(n \log n)\) in the size \(n\) of the input. More specifically, the algorithm performs \(n\log n+2.996n+o(n)\) comparisons and \(n\log n+2.645n+o(n)\) element moves on the average. An experimental comparison of our proposed algorithm with the most efficient variants of Quicksort and Heapsort is carried out and its results are discussed.