If you use the median of three or five randomly selected points, the worst case/average case distinction is not going to come up. You could even use the first, middle, end and two randomly selected points if you get nutty about it.
On Thu, Sep 23, 2010 at 11:57 AM, Luc Maisonobe <luc.maison...@free.fr>wrote: > Partition-based algorithms are O(n) in expected time but not in worst > case time. If end users ask for it later, we could improve again by > adding the Musser's introselect that guarantees O(n) behavior even in > worst case. >
