Here is a sort template (that can very easily be turned into a C
routine).
It is an introspective sort. Bentley & McIlroy proved that every qsort
routine will degrade into quadratic behavior with a worst-case input.
This function detects quadratic behavior and switches to qsort when
needed.
Use of this template is totally unrestricted.
I sent a copy to the author of FastDB and it is what he uses for
ordering data, as he found it to be an excellent performer.
It uses all the standard tricks to ensure good performance.
> -----Original Message-----
> From: pgsql-hackers-owner@postgresql.org [mailto:pgsql-hackers-
> owner@postgresql.org] On Behalf Of Qingqing Zhou
> Sent: Tuesday, December 13, 2005 10:29 AM
> To: Luke Lonergan
> Cc: Tom Lane; Neil Conway; Bruce Momjian; pgsql-hackers@postgresql.org
> Subject: Re: [HACKERS] Which qsort is used
>
>
>
> On Mon, 12 Dec 2005, Luke Lonergan wrote:
> >
> > Might you have time to implement these within the testing framework
I
> > published previously? It has both the NetBSD and qsortG included
along
> with
> > a timing routine, etc.
> >
>
> Here we go:
>
> http://www.cs.toronto.edu/~zhouqq/postgresql/sort/sort.html
>
> The source tar ball and linux 2.4G gcc 2.96 test results is on the
page.
> There is a clear loser glibc, not sure qsortB or qsortG which is
better.
>
> Regards,
> Qingqing
>
> ---------------------------(end of
broadcast)---------------------------
> TIP 2: Don't 'kill -9' the postmaster