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?
Comments
I really like the randomization solution. Worst case? What worst case?
Well, the worst case is still there. You're just going to have a very hard time crafting an input that triggers it.