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

On Sat, Mar 9, 2013 at 10:22 PM, Dann Corbit <DCorbit(at)connx(dot)com> wrote:
> 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.

Hm, I was using the terminology differently than the Wikipedia page. I
was referring to the recursive median of 5s used as the pivot
selection as "median of medians". And I still called Quicksort or
Quickselect using that pivot Quicksort or Quickselect with that
specific pivot choice algorithm.

When using that pivot choice Quicksort is O(n*log(n)) and Quickselect
(Median of Medians on Wikipedia) is O(n). But the constant factor
becomes larger than if the pivot choice algorithm is O(1). I suppose
it's more interesting in the case of Quickselect since there's no
other alternative algorithms that could be used that have better
constant factors whereas for sorting we have other options.

I wonder if it makes sense to use timsort as the fallback for
quicksort if the partition sizes are skewed. Timsort is specifically
designed to handle presorted inputs well. On the other hand it is
itself a hybrid sort so it might be getting overly complex to make it
part of a hybrid algorithm.

--
greg