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(at)gmail(dot)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(at)momjian(dot)us> http://momjian.us
EnterpriseDB http://enterprisedb.com

+ It's impossible for everything to be true. +