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: [EMAIL PROTECTED] [mailto:pgsql-hackers- > [EMAIL PROTECTED] 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
iqsort.h
Description: iqsort.h
---------------------------(end of broadcast)--------------------------- TIP 1: if posting/reading through Usenet, please send an appropriate subscribe-nomail command to [EMAIL PROTECTED] so that your message can get through to the mailing list cleanly