I've been looking for a proof of why an even split is the best case for the quicksort algorithm. Every anaylsis of the algorithm I've seen simply states that "the best case occurs when the partitions are as evenly balanced as possible" but stops short of proving why an even split is better than any other.
Obviously this is true, but I want to know why. How did we arrive at the knowledge that even splits are fast and uneven splits are slow?
Suppose the partition sizes are in some proportion 0 ≤ p ≤ 1, so that an array of length n is split into two parts which are, roughly, length pn and (1 − p)n respectively. Then we can write the recurrence relation for the running time:
T(n) = T(pn) + T((1 − p)n) + O(n)
This equation has a solution of the form T(n) = O(n log n) whenever 0 < p < 1, whereas when p is 0 or 1 the time complexity is quadratic instead. So let's consider just one layer of recursion, knowing that the formula is like T(n) ~ n log n. This also means we don't necessarily assume that other recursive calls must partition in the same proportion p. We can ignore the constant factor and the lower-order terms for this analysis, giving:
T(n) = pn log pn + (1 − p)n log (1 − p)n + O(n)
The part of this which depends on p is just the middle two terms, which expand to:
pn (log p + log n) + (1 − p)n (log (1 − p) + log n)
Some of this cancels out:
pn log p + (1 − p)n log (1 − p) + n log n
We want to find p minimising this, so we can ignore the factor of n and the final n log n term which does not depend on p, so we are minimising
p log p + (1 − p) log (1 − p)
It can then be seen (e.g. on Wolfram Alpha) that this is minimised when p = 0.5.