Re: Why do we still perform a check for pre-sorted input within qsort variants?

On Mon, Feb 25, 2013 at 02:31:21PM +0000, Peter Geoghegan wrote:
> 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.

Perhaps we are more likely to be fed sorted data than a typical qsort
usecase.

--  Bruce Momjian  <bruce@momjian.us>        http://momjian.us EnterpriseDB
http://enterprisedb.com
 + It's impossible for everything to be true. +