> Random pivot selection will certainly result in more frequent lopsided
> partitions without any malicious intent.
Yep. It makes "adversary input" attacks more or less impossible, at the
price of higher average cost. Maybe a less randomized version would do,
i.e. select randomly one of the "3" medians found, but would keep some
nice better performance property. It would need proof, though.
--
Fabien.