On 1/22/15 4:26 PM, H. S. Teoh via Digitalmars-d wrote:
The question, though, is whether this hybrid recursion actually wins us anything, since heapsort is known to be somewhat slower than quicksort. In the worst case, you choose a poor pivot and get*both* the worst case of quicksort and the inferior performance of heapsort compounded together.
The glass-half-full view of this is you combine the advantages of quicksort and heapsort :o).
Unless there's a way to modify heapsort to be more efficient as well? Actually, another idea occurred to me: suppose we modify partition() instead, so that instead of partitioning in-place, it deposits partitioned elements into a target (possibly overlapping) range. Then we modify the right-recursion, so that its partitioning step actually simultaneously moves the range over to the target area for us. Not sure if this will eliminate the copying cost, but it might, since partition has to traverse the entire subrange anyway.
That's interesting! Andrei
