> -----Original Message-----
> From: pgsql-hackers-owner@postgresql.org [mailto:pgsql-hackers-
> owner@postgresql.org] On Behalf Of Qingqing Zhou
> Sent: Friday, December 16, 2005 5:14 PM
> To: Bruce Momjian
> Cc: Luke Lonergan; Tom Lane; Neil Conway; pgsql-hackers@postgresql.org
> Subject: Re: [HACKERS] Re: Which qsort is used
>
> On Fri, 16 Dec 2005, Bruce Momjian wrote:
>
> >
> > At this point, I think we have done enough testing on enough
platforms
> > to just use port/qsort on all platforms in 8.2. It seems whenever
> > someone tries to improve the BSD qsort, they make it worse.
> >
>
> Not necessariliy true. Dann Corbit sent me an implementation a while
ago
> (you can see it on the same site). BSD qsort is improved, though not
that
> much, by two methods. Since Dann write the program from scratch, so I
am
> not sure if we are afford to take the efforts for the improvement.
Both of them are modified versions of Bentley's sort algorithm.
I just added the in-order check to both of them, and the reversed
partition check for the second method (in the case of the subfiles
because insertion sort is allergic to reversed partitions).
At any rate, neither is much of an improvement on Bentley's version.
For the rare cases of completely ordered or completely reversed, it will
be a monumental improvement. But that is a pretty rare case.
If I could use C++, I could do much better. It is very difficult for me
to write an ADT in C instead of in C++.