Quicksort with median in O(n log n)

I don't really understand why we don't just always select the median element as the pivot. This can be done in O(n) and thus results in a to开发者_StackOverflow社区tal run time of O(n log n).

I just assume that probably there is a large constant hidden in the O(n) for the median search.

From the Wikipedia Quicksort page:

Conversely, once we know a worst-case selection algorithm is available, we can use it to find the ideal pivot (the median) at every step of quicksort, producing a variant with worst-case O(n log n) running time. In practical implementations, however, this variant is considerably slower on average.

In other words, the cost of forcing it to be guaranteed O(n log n) is generally not worth paying. There's more information on that page, as well as on the selection algorithms page.

use randomized quicksort and you have worstcase run time of O(n log n) with very high probability.

Apparently it seems that the running time of finding the median is O(n) using randomized version of partition, but actually when the partition is again unbalanced at its extreme then the running time goes to O(n²). So you can make no improvement right from here. But still there's a hope. If you go through "CORMEN" then you will find that finding ith order statistic can be done in linear time even in worst case scenario. The technique that is used is to use the median of median as the pivot element and then find the nedian which guarantees the linear running time in any case. So we can use that technique in quicksort also to get O(nlgn) running time