We know about Quick Sort and Randomized Version and Partition. I ran into a Fact when I read my notes.
Let $0 < a < 0.5$ be some constant. We have an $n$-element array as input. Randomized quicksort chooses one element from array uniformly at random as a pivot and partitions. With probability $1-2a$ the smallest section be greater than $an$.
How this probability is calculated?
You are looking for the probability that the smaller of the two sections contains more than fraction $a$ of the array.
If the pivot element is selected uniformly at random from the array, then one section will contain fraction $X$ of the array, and the other will contain fraction $1-X$, where $X$ has uniform distribution over the interval $[0,1]$. So the desired probability is $$P(\min(X,1-X)>a)$$ which has probability $1-2a$ because $$\min(X,1-X)>a\ \Longleftrightarrow\ a<X<1-a\;.$$
