X-Original-To: pgsql-hackers-postgresql.org@localhost.postgresql.org
Received: from localhost (av.hub.org [200.46.204.144])
	by postgresql.org (Postfix) with ESMTP id 28EBC9DC95D;
	Thu, 16 Feb 2006 09:08:48 -0400 (AST)
Received: from postgresql.org ([200.46.204.71])
	by localhost (av.hub.org [200.46.204.144]) (amavisd-new, port 10024)
	with ESMTP id 86594-08; Thu, 16 Feb 2006 09:08:51 -0400 (AST)
Received: from svr4.postgresql.org (svr4.postgresql.org [66.98.251.159])
	by postgresql.org (Postfix) with ESMTP id 27E5D9DC8AF;
	Thu, 16 Feb 2006 09:08:46 -0400 (AST)
Received: from mail.aeccom.com (port-83-236-156-26.static.qsc.de
	[83.236.156.26])
	by svr4.postgresql.org (Postfix) with ESMTP id 703B15AF085;
	Thu, 16 Feb 2006 13:08:49 +0000 (GMT)
Received: from localhost (localhost.localdomain [127.0.0.1])
	by mail.aeccom.com (Postfix) with ESMTP id AEF431C16A;
	Thu, 16 Feb 2006 14:08:43 +0100 (CET)
Received: from mail.aeccom.com ([127.0.0.1])
	by localhost (gate6.aeccom.com [127.0.0.1]) (amavisd-new, port 10024)
	with LMTP id 21212-01; Thu, 16 Feb 2006 14:08:42 +0100 (CET)
Received: from [192.168.2.14] (andes.core.aeccom.com [192.168.2.14])
	by mail.aeccom.com (Postfix) with ESMTP id C1A8C1C0AB;
	Thu, 16 Feb 2006 14:08:42 +0100 (CET)
Message-ID: <43F47958.8000605@aeccom.com>
Date: Thu, 16 Feb 2006 14:08:40 +0100
From: Sven Geisler <sgeisler@aeccom.com>
Organization: AEC/communications GmbH
User-Agent: Thunderbird 1.5 (Windows/20051201)
MIME-Version: 1.0
To: Martijn van Oosterhout <kleptog@svana.org>
Cc: Florian Weimer <fw@deneb.enyo.de>,
	Neil Conway <neilc@samurai.com>, Tom Lane <tgl@sss.pgh.pa.us>,
	Gary Doades <gpd@gpdnet.co.uk>, pgsql-performance@postgresql.org,
	pgsql-hackers@postgresql.org
Subject: Re: [PERFORM] qsort again
References: <43F38867.6010701@gpdnet.co.uk> <19510.1140036968@sss.pgh.pa.us>
	<19779.1140038874@sss.pgh.pa.us> <43F39E53.1020009@gpdnet.co.uk>
	<20781.1140046109@sss.pgh.pa.us>
	<1140055972.31672.42.camel@localhost.localdomain>
	<873bijsdvb.fsf@mid.deneb.enyo.de>
	<20060216124918.GE26127@svana.org>
In-Reply-To: <20060216124918.GE26127@svana.org>
Content-Type: text/plain; charset=ISO-8859-15; format=flowed
Content-Transfer-Encoding: 7bit
X-Virus-Scanned: amavisd-new at aeccom.com
X-Virus-Scanned: by amavisd-new at hub.org
X-Spam-Status: No, score=0 required=5 tests=[none]
X-Spam-Score: 0
X-Spam-Level: 
X-Archive-Number: 200602/618
X-Sequence-Number: 79756

Martijn van Oosterhout schrieb:
> 
> Last time around there were a number of different algorithms tested.
> Did anyone run those tests while getting it to count the number of
> actual comparisons (which could easily swamp the time taken to do the
> actual sort in some cases)?
> 

The last time I did such tests is almost 10 years ago. I had used 
MetroWerks CodeWarrior C/C++, which had Quicksort as algorithm in the Lib C.
Anyhow, I tested a few algorithms including merge sort and heapsort. I 
end up with heapsort because it was the fastest algorithm for our issue. 
We joined two arrays where each array was sorted and run qsort to sort 
the new array.

Sven.