Re: qsort, once again

I have seen a lot of dumb "fixes" to sort routines.

In a commercial sort function I saw some time ago, the check for a
condition that causes qsort to go quadratic was removed. There was a
comment there that said the engineer "didn't see any improvement in
performance". Of course, the check was not there to improve performance
but to prevent disaster.

Obviously, he failed to check some very important data sets. If a sort
routine cannot handle (among other things):
1. Already sorted
2. Almost sorted
3. Reverse sorted
4. Organ pipe ( the inspiration for "Engineering a Sort Function" )
5. Small number of distinct values

Then it will cause problems in real-life use.

> -----Original Message-----
> From: Tom Lane [mailto:tgl(at)sss(dot)pgh(dot)pa(dot)us]
> Sent: Thursday, March 16, 2006 12:09 PM
> To: Dann Corbit
> Cc: Jonah H. Harris; pgsql-hackers(at)postgresql(dot)org; Jerry Sievers
> Subject: Re: [HACKERS] qsort, once again
>
> "Dann Corbit" <DCorbit(at)connx(dot)com> writes:
> > I sent him a copy
>
> Thanks. This is really interesting: the switch to insertion sort on
> perfect pivot is simply not there in Bentley & McIlroy's paper. So
> it was added later, and evidently not tested as carefully as it should
> have been. At this point I'm more than half tempted to take it out
> entirely.
>
> So we still have a problem of software archaeology: who added the
> insertion sort switch to the NetBSD version, and on what grounds?
>
> regards, tom lane