3 ms·
Isn't the point of quicksort that the randomization of the pivot selection means that you're extremely unlikely to run into a pathological case for the specific
by sn9 3y ago
Isn't the point of quicksort that the randomization of the pivot selection means that you're extremely unlikely to run into a pathological case for the specific pivot chosen?
And perhaps even more unlikely if you permute the input sequence before sorting it.
I'm basing this off of my understanding of Skiena's discussion of quicksort in The Algorithm Design Manual.