On Mon, Mar 19, 2012 at 7:23 PM, Robert Haas <robertmhaas@gmail.com> wrote:
> On Sun, Mar 18, 2012 at 11:25 AM, Tom Lane <tgl@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
