$\star$ Argue that for any constant $0 < \alpha \le 1/2$, the probability is approximately $1 - 2\alpha$ that on a random input array,
PARTITIONproduces a split more balanced than $1 - \alpha$ to $\alpha$.
Oh, this is nice!
In order to produce a worse split than $\alpha$ to $1 - \alpha$,
must pick a pivot that will be either within the smallest $\alpha n$ elements
or the largest $\alpha n$ elements. The probability of either is
(approximately) $\alpha n / n = \alpha$ and the probability of both is
$2\alpha$. Thus, the probability of having a better partition is the complement,
$1 - 2\alpha$.