3 ms·
It depends on how you implement median selection. You can get O(n log n) worst case if you want.
by zeroonetwothree 11y ago
It depends on how you implement median selection. You can get O(n log n) worst case if you want.
- pjscott 11y agoTrue, 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 https://en.wikipedia.org/wiki/Introsort