develooper Front page | perl.perl5.porters | Postings from September 2009

Re: dual pivot quicksort

Thread Previous | Thread Next
David Nicol
September 25, 2009 11:47
Re: dual pivot quicksort
Message ID:
On Fri, Sep 25, 2009 at 9:58 AM, Nicholas Clark <> 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.
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

Thread Previous | Thread Next Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at | Group listing | About