On Mon, Jul 1, 2013 at 4:32 PM, Robert Haas <robertmh...@gmail.com> wrote: >> This shouldn't be too complex, and should give us a fixed nlogn complexity >> even for wild data sets, without affecting existing normal data sets that >> are present in every day transactions. I even believe that those data sets >> will also benefit from the above optimisation. > > The only method of selecting a pivot for quicksort that obtain O(n lg > n) run time with 100% certainty is have a magical oracle inside the > computer that tells you in fixed time and with perfect accuracy which > pivot you should select.
Doesn't a linear median algorithm (say median of medians) get you O(n lg n)? Granted, with a huge constant (I think 4)... but it should still be O(n lg n). -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
