Re: dual pivot quicksort

On Fri, Sep 25, 2009 at 9:58 AM, Nicholas Clark <nick@ccl4.org> wrote:



> Plus, of course, the dual-pivot is not stable.  We've
> promised a stable implementation.  If you (or at least I)
> try to stabilize quicksort, you eliminate the appearance
> of any duplicated items, which, according to the timings
> at the bottom of 2), are where quicksort gets the big
> edge over random data.
>
> So I won't be rushing to modify the quicksort implementation,
> but if anybody else thinks that would be fun or rewarding,
> I would certainly encourage it.  Should at least be worth a
> paper.  -- jpl


I came up with a way to stabilize quicksort earlier this year, with
the same number of comparisons. It relies on a rich list api for the
partitions, though, instead of swapping.

http://cpansearch.perl.org/src/DAVIDNICO/Tie-Quicksort-Lazy-0.04/lib/Tie/Quicksort/Lazy.pm
implements it in Perl to provide lazy sorting.

instead of swapping, new data structures are provided for the
partitions, and they are never destabilized.


-- 
"A 50%-good solution that people actually have solves more problems
and survives longer than a 99% solution that nobody has because it’s
in your lab where you’re endlessly polishing the damn thing. Shipping
is a feature. A really important feature. Your product must have it."
-- Joel Spolsky

• dual pivot quicksort by Nicholas Clark
• Re: dual pivot quicksort by Abigail
• Re: dual pivot quicksort by David Nicol
• Re: dual pivot quicksort by demerphq