[Someone]

> If I'm understanding correctly, the median is actually guaranteed to be in the larger of the two pieces of the array after partitioning.

Only in the first iteration. There’s a good chance it will be in the smaller one in the second iteration, for example.

So, your analysis is a bit too harsh, but probably good enough for a proof that it’s O(n) on average.

> Heavily skewed distributions would perform pretty badly

That’s why I used the weasel worlds “real world data” ;-)

I also thought about mentioning that skew can be computed streaming (see for example https://www.boost.org/doc/libs/1_53_0/doc/html/accumulators/...), but even if you have that, there still are distributions that will perform badly.