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

On Sat, Mar 9, 2013 at 8:52 PM, Dann Corbit <DCorbit(at)connx(dot)com> wrote:
> Median of medians selection of the pivot gives you O(n*log(n)).
>
> No. It does make O(n*n) far less probable, but it does not eliminate it. If it were possible, then introspective sort would be totally without purpose.

No really, quicksort with median of medians pivot selection is most
definitely O(n*log(n)) worst case. This is textbook stuff. In fact even the
introspective sort paper mentions it as one of the options to fail
over to if the partition size isn't decreasing rapidly enough.

The problem is that median of medians is O(n) rather than O(1). That
doesn't change the O() growth rate since there will be log(n)
iterations. But it means it contributes to the constant factor and the
end result ends up being a constant factor larger than heap sort or
merge sort. That also explains how your reference on the quicksort
adversary doesn't apply. It works by ordering elements you haven't
compared yet and assumes that all but O(1) elements will still be
eligible for reordering.

In any case I think you're basically right. What we have is basically
a broken introspective sort that does more work than necessary and
then handles fewer cases than it should. Implementing a better
introspection that detects all perverse cases and does so with a lower
overhead than the current check is a fine idea.

--
greg