[zeroonetwothree]

It depends on how you implement median selection. You can get O(n log n) worst case if you want.

[pjscott]

True, though it's usually not worth the hassle. Most production implementations of quicksort just drop down to heapsort for the current sub-array if the stack gets too deep.

https://en.wikipedia.org/wiki/Introsort