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

Yes, you are right. I knew of a median of medians technique for pivot selection and I mistook that for the median of medians median selection algorithm (which it definitely isn't).
I was not aware of a true linear time selection of the median algorithm {which is what median of medians accomplishes). The fastest median selection algorithm that I was aware of was quickselect, which is only linear on average.
I think that you analysis is correct, at any rate.

I also think I will enjoy learning and experimenting with the median of medians algorithm.
I found a link about it here:
http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm

-----Original Message-----
From: gsstark(at)gmail(dot)com [mailto:gsstark(at)gmail(dot)com] On Behalf Of Greg Stark
Sent: Saturday, March 09, 2013 1:21 PM
To: Dann Corbit
Cc: Bruce Momjian; Peter Geoghegan; Robert Haas; Tom Lane; PG Hackers
Subject: 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