> 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?