Robert Haas <robertmhaas@gmail.com> writes:
> On Fri, Jun 15, 2012 at 12:22 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> (And from a performance standpoint, I'm not entirely convinced it's not
>> a bug, anyway. Worst-case behavior could be pretty bad.)
> Instead of simply asserting that, could you respond to the specific
> points raised in my analysis? I think there's no way it can be bad.
> I am happy to be proven wrong, but I like to understand why it is that
> I am wrong before changing things.
Maybe I missed something, but as far as I saw your argument was not that
the performance wasn't bad but that the rest of the sort code would
dominate the runtime anyway. I grant that entirely, but that doesn't
mean that it's good for this piece of it to possibly have bad behavior.
In any case, it seems to me that if the bottom line is that the
performance of this piece of code isn't going to matter overall,
then we might as well use the simplest, least surprising implementation
we can. And I concur with Peter that a doubling-based approach meets
that description, while what you've got here doesn't.
regards, tom lane