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:mkoi-pg@aon.at]
> 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