An interesting article on sorting and comparison count: http://www.acm.org/jea/ARTICLES/Vol7Nbr5.pdf
Here is the article, the code, and an implementation that I have been toying with: http://cap.connx.com/chess-engines/new-approach/algos.zip Algorithm quickheap is especially interesting because it does not require much additional space (just an array of integers up to size log(element_count) and in addition, it has very few data movements. > -----Original Message----- > From: Manfred Koizar [mailto:[EMAIL PROTECTED] > Sent: Thursday, December 22, 2005 1:59 PM > To: Martijn van Oosterhout > Cc: Tom Lane; Dann Corbit; Qingqing Zhou; Bruce Momjian; Luke Lonergan; > Neil Conway; pgsql-hackers@postgresql.org > Subject: Re: [HACKERS] Re: Which qsort is used > > On Thu, 22 Dec 2005 08:01:00 +0100, Martijn van Oosterhout > <kleptog@svana.org> wrote: > >But where are you including the cost to check how many cells are > >already sorted? That would be O(H), right? > > Yes. I didn't mention it, because H < N. > > > This is where we come back > >to the issue that comparisons in PostgreSQL are expensive. > > So we agree that we should try to reduce the number of comparisons. > How many comparisons does it take to sort 100000 items? 1.5 million? > > >Hmm, what are the chances you have 100000 unordered items to sort and > >that the first 8% will already be in order. ISTM that that probability > >will be close enough to zero to not matter... > > If the items are totally unordered, the check is so cheap you won't > even notice. OTOH in Tom's example ... > > |What I think is much more probable in the Postgres environment > |is almost-but-not-quite-ordered inputs --- eg, a table that was > |perfectly ordered by key when filled, but some of the tuples have since > |been moved by UPDATEs. > > ... I'd not be surprised if H is 90% of N. > Servus > Manfred ---------------------------(end of broadcast)--------------------------- TIP 2: Don't 'kill -9' the postmaster
