Quicksort
Using percentiles

If each pivot has rank somewhere in the middle 50 percent, that is, between the 25th percentile and the 75th percentile, then it splits the elements with at least 25% and at most 75% on each side. If we could consistently choose such pivots, we would only have to split the list at most log 4 / 3 n {\displaystyle \log _{4/3}n} times before reaching lists of size 1, yielding an O (n log n) algorithm.

When the input is a random permutation, the pivot has a random rank, and so it is not guaranteed to be in the middle 50 percent. However, when we start from a random permutation, in each recursive call the pivot has a random rank in its list, and so it is in the middle 50 percent about half the time. That is good enough. Imagine that a coin is flipped: heads means that the rank of the pivot is in the middle 50 percent, tail means that it isn't. Now imagine that the coin is flipped over and over until it gets k heads. Although this could take a long time, on average only 2 k flips are required, and the chance that the coin won't get k heads after 100 k flips is highly improbable (this can be made rigorous using Chernoff bounds). By the same argument, Quicksort's recursion will terminate on average at a call depth of only 2 log 4 / 3 n {\displaystyle 2\log _{4/3}n}. But if its average call depth is O (log n), and each level of the call tree processes at most n elements, the total amount of work done on average is the product, O (n log n). The algorithm does not have to verify that the pivot is in the middle half—if we hit it any constant fraction of the times, that is enough for the desired complexity.
length_constraints:number_paragraphs[4]