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?
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)).