[btilly]

You can trivially achieve bounded worst case performance with minimal overhead by doing median of medians only, say, one time in 5.

In the average case you do the expensive median of medians on a small fraction of the data and so only pay a few percent average penalty. And in the worst case you still get n log(n) performance.

[judk]

How is the worst case not n^2 on a case you don't use medians of medians?

[adrianN]

Every fifth pivot is chosen to be an actual median.