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

Peter Geoghegan <peter(dot)geoghegan86(at)gmail(dot)com> writes:
> In the past, Robert and I have criticised the fact that our qsort
> implementation (and the various specialisations thereof) each perform
> a check for pre-sorted input. This check does not appear in the
> original NetBSD qsort that we lifted our implementation from, and
> presumably isn't described by the document 'Qsort routine from Bentley
> & McIlroy's "Engineering a Sort Function"' that that implementation is
> based on.

FWIW, I've been suspicious of that pre-sorted check since the day it
went in. Bentley was my faculty adviser for awhile in grad school,
and I know him to be *way* too smart to have missed anything as simple
as that. But I didn't have hard evidence on which to object to it
at the time, and indeed testing seemed to say it was a good idea:
http://www.postgresql.org/message-id/18732.1142967137@sss.pgh.pa.us

If you can provide a refutation I will gladly see it out of there.

regards, tom lane