You just described the best deterministic algorithm, but it turns out there are even better randomized algorithms, where you "flip a coin" when deciding to look up StackOverflow or keep learning (of course, that may or may not be practical :p).
You just described the best deterministic algorithm, but it turns out there are even better randomized algorithms, where you "flip a coin" when deciding to look up StackOverflow or keep learning (of course, that may or may not be practical :p).
Hmm... given that you stated that the best randomized algorithms we have beat our best deterministic ones, isn't there a place for even better deterministic algorithm?
Am I missing some critical piece of understanding here?
if we pick the pivot to always be the first element, then any sorted array will cause worst-case running time. But by randomizing the pivot, we can do well (in expectation) for any input.
Iow, if you can never do X, then you cannot write any algorithm that may do X.