Postgres Pro
Downloads
Home   >   mailing lists

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

From Greg Stark
Subject Re: Why do we still perform a check for pre-sorted input within qsort variants?
Date
Msg-id CAM-w4HOnPpoqLq0Vsu-BgpZY7wftGOTdXs=MX1oujgy4jbhqEQ@mail.gmail.com
Whole thread Raw
In response to Re: Why do we still perform a check for pre-sorted input within qsort variants?  (Dann Corbit <DCorbit@connx.com>)
Responses Re: Why do we still perform a check for pre-sorted input within qsort variants?  (Dann Corbit <DCorbit@connx.com>)
List pgsql-hackers
Tree view 
On Sat, Mar 9, 2013 at 10:32 AM, Dann Corbit <DCorbit@connx.com> wrote:
> There is no such thing as a quicksort that never goes quadratic.  It was formally proven

The median of medians selection of the pivot gives you O(n*log(n)).

-- 
greg

pgsql-hackers by date:

Previous
From: Fujii Masao
Date:
Subject: Re: Support for REINDEX CONCURRENTLY
Next
From: Fujii Masao
Date:
Subject: Re: Support for REINDEX CONCURRENTLY