<p>Quicksort-Heapsort in-place hybrids are really interesting, too, since most of them only needs n*log n comparisons in the worst case (they are optimal with respect to the first term of the asymptotics, so they avoid the worst-case scenarios of Quicksort), O(log n) extra-space and they preserve at least "a half" of the good behaviour of Quicksort with respect to already-ordered set of data. An extremely interesting algorithm is presented by Dikert and Weiss in <a href="http://arxiv.org/pdf/1209.4214v1.pdf" rel="noreferrer">http://arxiv.org/pdf/1209.4214v1.pdf</a>:</p>

<ul>
<li>Select a pivot p as the median of a random sample of sqrt(n) elements (this can be done in at most 24 sqrt(n) comparisons through the algorithm of Tarjan&amp;co, or 5 sqrt(n) comparisons through the much more convoluted spider-factory algorithm of Schonhage);</li>
<li>Partition your array in two parts as in the first step of Quicksort;</li>
<li>Heapify the smallest part and use O(log n) extra bits to encode a heap in which every left child has a value greater than its sibling;</li>
<li>Recursively extract the root of the heap, sift down the lacune left by the root until it reaches a leaf of the heap, then fill the lacune with an appropriate element took from the other part of the array;</li>
<li>Recur over the remaining non-ordered part of the array (if p is chosen as the exact median, there is no recursion at all).</li>
</ul>
Quicksort vs heapsort
<p>Both quicksort and heapsort do in-place sorting. Which is better? What are the applications and cases in which either is preferred?</p>