[BetaCygni]

> An attempt to solve this problem has been randomization as shown already in Hoare’s first articles on Quicksort [1]. On the other hand, this does not change the statistical probability for bad cases.

I really like the randomization solution. Worst case? What worst case?

[matslina]

Well, the worst case is still there. You're just going to have a very hard time crafting an input that triggers it.