Re: Why do we still perform a check for pre-sorted input within qsort variants?

-----Original Message-----
From: Peter Geoghegan [mailto:peter.geoghegan86@gmail.com]
Sent: Friday, March 08, 2013 12:00 PM
To: Bruce Momjian
Cc: Dann Corbit; Robert Haas; Tom Lane; PG Hackers
Subject: Re: [HACKERS] Why do we still perform a check for pre-sorted input within qsort variants?

On 8 March 2013 11:48, Bruce Momjian <bruce@momjian.us> wrote:
> On Fri, Mar 8, 2013 at 07:43:10PM +0000, Dann Corbit wrote:
>> I seem to recall that a year or two back some study was done on
>> quicksort methodology as used in PostgreSQL.  As I recall, the
>> algorithm used in PostgreSQL fared well in the tests.
>
> Well, that's good to hear.

I wouldn't mind taking a look at that. We're not the only ones that use (more or less) that same algorithm. I noticed
thatRedis does so too, just for example (though they didn't get wise to the problems with the "swap_cnt"
pessimisation).

>>
Turns out, it was a lot longer ago than I thought (2005!).  The thread was called "Which qsort is used", but I also
seemto recall that the topic was revisited a few times.  See, for instance: 

http://www.postgresql.org/message-id/Pine.LNX.4.58.0512121138080.18520@eon.cs
http://www.cs.toronto.edu/~zhouqq/postgresql/sort/sort.html

<<