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 70BA69DCA02
	for <pgsql-hackers-postgresql.org@localhost.postgresql.org>;
	Thu, 16 Feb 2006 10:19:43 -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 05143-02
	for <pgsql-hackers-postgresql.org@localhost.postgresql.org>;
	Thu, 16 Feb 2006 10:19:46 -0400 (AST)
X-Greylist: domain auto-whitelisted by SQLgrey-
Received: from nproxy.gmail.com (nproxy.gmail.com [64.233.182.193])
	by postgresql.org (Postfix) with ESMTP id A34F89DC9CD
	for <pgsql-hackers@postgresql.org>;
	Thu, 16 Feb 2006 10:19:40 -0400 (AST)
Received: by nproxy.gmail.com with SMTP id a27so107718nfc
	for <pgsql-hackers@postgresql.org>;
	Thu, 16 Feb 2006 06:19:44 -0800 (PST)
DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=beta; d=gmail.com;
	h=received:message-id:date:from:to:subject:cc:in-reply-to:mime-version:content-type:references;
	b=LiZtTXX6BxR2gmpb5zWyTWgmkaPF67oTmQf8//DZIO9oMsKdeWZNCDFgr6rLbC4aGHUA6m/dO4sd/+oJBqhoClwqCc6KoSCcsgl9U04L1I3shOSe/v1tuz6K/XtoqIx59J3jwycPZc/SRY0CqzKKV85287LtYWgJPvHeEXEnlOo=
Received: by 10.49.51.13 with SMTP id d13mr172400nfk;
	Thu, 16 Feb 2006 06:19:44 -0800 (PST)
Received: by 10.48.219.16 with HTTP; Thu, 16 Feb 2006 06:19:44 -0800 (PST)
Message-ID: <36e682920602160619n1f3752e4mb7a83c9dc9b045cf@mail.gmail.com>
Date: Thu, 16 Feb 2006 09:19:44 -0500
From: "Jonah H. Harris" <jonah.harris@gmail.com>
To: Markus Schaber <schabi@logix-tt.com>
Subject: Re: qsort again (was Re: [PERFORM] Strange Create Index
Cc: pgsql-performance@postgresql.org, pgsql-hackers@postgresql.org
In-Reply-To: <43F481CD.2010509@logix-tt.com>
MIME-Version: 1.0
Content-Type: multipart/alternative;
	boundary="----=_Part_253_7557059.1140099584155"
References: <43F38867.6010701@gpdnet.co.uk> <19779.1140038874@sss.pgh.pa.us>
	<43F39E53.1020009@gpdnet.co.uk> <20781.1140046109@sss.pgh.pa.us>
	<7.0.1.0.2.20060215194635.03b55da0@earthlink.net>
	<21615.1140052893@sss.pgh.pa.us>
	<7.0.1.0.2.20060215223710.03a7c618@earthlink.net>
	<20060216113522.GA3461@uio.no>
	<7.0.1.0.2.20060216071053.0385a1a8@earthlink.net>
	<43F481CD.2010509@logix-tt.com>
X-Virus-Scanned: by amavisd-new at hub.org
X-Spam-Status: No, score=0.215 required=5 tests=[AWL=0.214,
 HTML_MESSAGE=0.001]
X-Spam-Score: 0.215
X-Spam-Level: 
X-Archive-Number: 200602/623
X-Sequence-Number: 79761

------=_Part_253_7557059.1140099584155
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

Last night I implemented a non-recursive introsort in C... let me test it a
bit more and then I'll post it here for everyone else to try out.

On 2/16/06, Markus Schaber <schabi@logix-tt.com> wrote:
>
> Hi, Ron,
>
> Ron wrote:
>
> > ...and of course if you know enough about the data to be sorted so as t=
o
> > constrain it appropriately, one should use a non comparison based O(N)
> > sorting algorithm rather than any of the general comparison based
> > O(NlgN) methods.
>
> Sounds interesting, could you give us some pointers (names, URLs,
> papers) to such algorithms?
>
> Thanks a lot,
> Markus
>
>
>
> --
> Markus Schaber | Logical Tracking&Tracing International AG
> Dipl. Inf.     | Software Development GIS
>
> Fight against software patents in EU! www.ffii.org
> www.nosoftwarepatents.org
>
> ---------------------------(end of broadcast)---------------------------
> TIP 4: Have you searched our list archives?
>
>                http://archives.postgresql.org
>



--
Jonah H. Harris, Database Internals Architect
EnterpriseDB Corporation
732.331.1324

------=_Part_253_7557059.1140099584155
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

Last night I implemented a non-recursive introsort in C... let me test it a=
 bit more and then I'll post it here for everyone else to try out.<br><br><=
div><span class=3D"gmail_quote">On 2/16/06, <b class=3D"gmail_sendername">M=
arkus Schaber
</b> &lt;<a href=3D"mailto:schabi@logix-tt.com">schabi@logix-tt.com</a>&gt;=
 wrote:</span><blockquote class=3D"gmail_quote" style=3D"border-left: 1px s=
olid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">Hi,=
 Ron,
<br><br>Ron wrote:<br><br>&gt; ...and of course if you know enough about th=
e data to be sorted so as to<br>&gt; constrain it appropriately, one should=
 use a non comparison based O(N)<br>&gt; sorting algorithm rather than any =
of the general comparison based
<br>&gt; O(NlgN) methods.<br><br>Sounds interesting, could you give us some=
 pointers (names, URLs,<br>papers) to such algorithms?<br><br>Thanks a lot,=
<br>Markus<br><br><br><br>--<br>Markus Schaber | Logical Tracking&amp;Traci=
ng International AG
<br>Dipl. Inf.&nbsp;&nbsp;&nbsp;&nbsp; | Software Development GIS<br><br>Fi=
ght against software patents in EU! <a href=3D"http://www.ffii.org">www.ffi=
i.org</a> <a href=3D"http://www.nosoftwarepatents.org">www.nosoftwarepatent=
s.org</a><br><br>---------------------------(end of broadcast)-------------=
--------------
<br>TIP 4: Have you searched our list archives?<br><br>&nbsp;&nbsp;&nbsp;&n=
bsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <a href=3D=
"http://archives.postgresql.org">http://archives.postgresql.org</a><br></bl=
ockquote></div><br><br clear=3D"all"><br>-- <br>Jonah H. Harris, Database I=
nternals Architect
<br>EnterpriseDB Corporation<br>732.331.1324<br>

------=_Part_253_7557059.1140099584155--