On 25 February 2013 11:49, Robert Haas <robertmhaas@gmail.com> wrote:
> I did attempt to do some tinkering with this while I was playing with
> it, but I didn't come up with anything really compelling. You can
> reduce the number of comparisons on particular workloads by tinkering
> with the algorithm, but then somebody else ends up doing more
> comparisons, so it's hard to say whether you've really made things
> better. Or at least I found it so.
Right.
To be honest, the real reason that it bothers me is that everything
else that our qsort routine does that differs from classic quicksort
(mostly quadratic insurance, like the median-of-medians pivot
selection, but also the fallback to insertion sort when n < 7) is very
well supported by peer reviewed research. Like Tom, I find it
implausible that Sedgewick and others missed a trick, where we did
not, particularly with something so simple.
--
Regards,
Peter Geoghegan