Regarding Quick Sort Killer

Some of you might have stumbled upon this cute article - http://igoro.com/archive/quicksort-killer/ \

What is really interesting is how he fixes quick sort to perform in O(N log N) against the defined adversary.

the quicksort might choose the median element as the pivot at each step, thus always geting a perfect split of the input sequence into two halves. Median can be found deterministically in O(N) running time, and so the total running time is always O(N log N).

My question is won't the linear time median-finding algorithm end up using the same compare function and perform in O(N^2) instead of O(N)?

Edit:

To be precise: I am questioning the complexity of the partition-based-median-selection algorithm开发者_运维问答 which uses a strategy similar to that of quick sort and it will use the same compare function as the one quick sort uses. How can it work in O(N) with this adversary?

won't the linear time median-finding algorithm end up using the same compare function and perform in O(N^2) instead of O(N)?

No, by adding an O(N) function to find the median the complexity becomes

O((N+N) log N) == O(2N log N) == O(N log N)

But, as that article states, the increased constant makes it unattractive.

The standard technique is called median-of-3 and a full median search won't really improve over that.

If worst case is critical, just don't use Quicksort. Shellsort has a better upperbound.