You can use the same idea in quicksort while choosing the pivot (and make it O(n log n)) but you don't because it is expensive. There is a very nice and simple

You can use the same idea in quicksort while choosing the pivot (and make it O(n log n)) but you don't because it is expensive. There is a very nice and simple probabilistic algorithm instead.