On Mon, Mar 19, 2012 at 7:23 PM, Robert Haas <robertmh...@gmail.com> wrote: > On Sun, Mar 18, 2012 at 11:25 AM, Tom Lane <t...@sss.pgh.pa.us> wrote: >> So has somebody found a hole in the n log n lower bound on the cost of >> comparison-based sorting? I thought that had been proven pretty >> rigorously. > > There's not much danger of anyone finding a way around that bound > since the proof is quite trivial, but keep in mind that it's a > worst-case bound.
Fwiw it also only holds for comparison sorts. If you can sort your items without actually comparing each item with the others then you aren't bound by it at all. Notably algorithms like radix sort and direct sort aren't bound by it and are O(n). I'm hoping to look at trying some of these for integer sorts when they apply using the new sort specialization code Peter added. -- greg -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
