Quicksort probabilistic analysis

Question

Let us say that we randomly pick up a pivot element and partition the array around it. What is the probability that we always pick the pivots in subsequent recursive calls such that it partitions the array in nearly two equal halves, till the time the array is completely sorted ?

Answer 1

I think it depends on what you mean by "nearly in two equal halves". It can be argued that "choosing a pivot from the middle third" satisfies the definition, in which case let's say $P_n$ is the probability that Quicksort chooses something in the middle third all the way down starting from a list of size $n$. Then we would get an estimate $P_n = \frac{1}{3} P_{n/3}^2$

The probability goes to $0$ as $n$ grows large.

For any definition of "nearly in two equal halves" that is more restrictive than this defininition e.g. "index in $[n/2-k, n/2+k]$" for some constant k, the probability will be even smaller and hence will also limit to $0$.