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

From: Greg Stark <stark(at)mit(dot)edu>
To: Dann Corbit <DCorbit(at)connx(dot)com>
Cc: Bruce Momjian <bruce(at)momjian(dot)us>, Peter Geoghegan <peter(dot)geoghegan86(at)gmail(dot)com>, Robert Haas <robertmhaas(at)gmail(dot)com>, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>, PG Hackers <pgsql-hackers(at)postgresql(dot)org>
Subject: Re: Why do we still perform a check for pre-sorted input within qsort variants?
Date: 2013-03-09 19:38:34
Message-ID: CAM-w4HOnPpoqLq0Vsu-BgpZY7wftGOTdXs=MX1oujgy4jbhqEQ@mail.gmail.com
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: pgsql-hackers

On Sat, Mar 9, 2013 at 10:32 AM, Dann Corbit <DCorbit(at)connx(dot)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

In response to

Responses

Browse pgsql-hackers by date

  From Date Subject
Next Message Fujii Masao 2013-03-09 19:50:15 Re: Support for REINDEX CONCURRENTLY
Previous Message Fujii Masao 2013-03-09 18:55:55 Re: Support for REINDEX CONCURRENTLY