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

-----Original Message-----
From: Peter Geoghegan [mailto:peter(dot)geoghegan86(at)gmail(dot)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(at)momjian(dot)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 that Redis 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 seem to 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

<<