On Fri, Mar 8, 2013 at 7:43 PM, Dann Corbit <DCorbit@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^12thoperations 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
yousure 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
