Wrap Up

Probability of getting lots of bad splits is very small. With high probability we divide the list into fractional pieces (instead of just nibbling off a constant-size piece). This is enough balance to get asymptotic $n \log n$ running time.

We could also prove an $n \log n$ lower bound on the expected running time (but we won't).