sortUniq

[Andrei Alexandrescu via Digitalmars-d]

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