Re: Why do we still perform a check for pre-sorted input within qsort variants?

On Fri, Mar 8, 2013 at 7:43 PM, Dann Corbit <DCorbit(at)connx(dot)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