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

Re: dual pivot quicksort

Thread Previous
September 25, 2009 10:51
Re: dual pivot quicksort
Message ID:
2009/9/25 Nicholas Clark <>:
> John said to forward his comments about dual pivot quicksort to the list, if
> I thought they were interesting. *I* thought that they were interesting :-)
> Nicholas Clark
> ----- Forwarded message from "John P. Linderman" <> -----
> Envelope-to:
> Delivery-date: Fri, 25 Sep 2009 14:56:30 +0100
> X-Mailer: exmh version 2.7.2 01/07/2005 (debian 1:2.7.2-16) with nmh-1.2
> Subject: Re: dual pivot quicksort
> In-reply-to: <>
> Comments: In-reply-to Nicholas Clark <>
>   message dated "Fri, 25 Sep 2009 13:52:00 +0100."
> Date: Fri, 25 Sep 2009 09:56:04 -0400
> From: "John P. Linderman" <>
>> I'm a bit confused whom we thank for Perl's current sort implementation.
> You can thank Tom for good parts of the quicksort implementation,
> Peter McIlroy for the good parts of the optimistic merge sort
> implementation, and me for any damage done to either.
>> However, as dual pivot quicksort appears to be the new black, I wondered if
>> either of you would consider it fun and rewarding to try to beat the current
>> implementation.
> Thanks!  I hadn't been keeping abreast of sorting theory.
> If I read 1) right,
> the improvements are solely in swaps, not in comparisons.
> 20% isn't chump change, but I'll wager that in perl, comparisons
> totally dominate the sort time (doesn't take long to swap
> a couple pointers relative to the time it takes to compare
> whatever is at them).  That may not be true for the timings
> is see in places like near the bottom of 2)

Has an interesting comment:

Several problems with this:

    * The implementation does not drop to a faster sort (e.g. optimal
sorting networks) for small n.
    * This has not been parallelized.
    * The new sort is slower on a third of the Server VM tests.

Using optimal sorting networks for small n will give much larger real
performance gains. Three-way recursion will degrade the performance of
a parallel implementation.

I bet perl sort is used on short lists /a lot/. Maybe precomputing a
set of optimal sorting networks for small size arrays is worth looking


perl -Mre=debug -e "/just|another|perl|hacker/"

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