3 ms·

Same goes for any implementation of quicksort with deterministic choice of pivot. It is possible to construct a DoS-type permutation to make it quadratic. > O(

by praptak 14y ago

Same goes for any implementation of quicksort with deterministic choice of pivot. It is possible to construct a DoS-type permutation to make it quadratic. > O(n^2) means very slow very quickly. You mean Theta(n^2) :-)

Derander 14y ago
If we're being really picky it is possible to deterministically find the median of n elements in \Theta(n) time so we're able to deterministically select as our pivot the median element. This gives deterministic \Theta(n log n). As mentioned elsewhere this algorithm has a fairly large constant factor and is not used in practice.