> 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 it

> 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/user_s_guide.html#accumulators.user_s_guide.the_statistical_accumulators_library 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.