On Fri, Mar 8, 2013 at 7:43 PM, Dann Corbit <dcor...@connx.com> wrote: > Checking for pre-sorted input will not make the routine faster on average. > However, it prevents a common perverse case where the runtime goes quadratic, > so sorting 10^6 elements will take K*10^12th operations when the bad > condition does occur. > Checking for pre-sorted data can be thought of as an insurance policy. It's > kind of a pain to pay the premiums, but you sure are glad you have it when an > accident occurs. > Because the check is linear, and the algorithm is O(n*log(n)), the cost is > not terribly significant.
Well pre-sorted inputs are not the only quadratic case. If we really wanted to eliminate quadratic cases we could implement the pivot choice algorithm that guarantees n*log(n) worst-case. But that will increase the average run-time. If we're not doing that then I think your whole argument falls apart. We do care about the average case as well as the worst-case. There's been a *ton* of research on sorting. I find it hard to believe there isn't a pretty solid consensus on which which of these defense mechanisms is the best trade-off. -- greg -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
