выбор опорного элемента в быстрой сортировке Хоара

[voipp]

Знающие люди утверждают, что на каждом этапе разбиения массива, опорный элемент надо выбирать случайным образом. Выбор постоянного грозит увеличением в среднем скорости работы. Утверждают они, что , например если выбирать опорным элементом крайний левый то в случае если массив отсортирован , то он заново будет отсортирован и сложность по времени - $n^2$, или если быть точнее $\frac{(1+n)}{2}n$. Вероятность такого случая $\frac{1}{n!}$.
Если мы будем выбирать опроный элемент случайно, то нам достаточно такого входного массива, что слева от опорного были все элементы меньше его, а справа - больше. Вероятность этого случая не меньше чем выше! Так в чем преимущество случайного опорного элемента.

[venco]

В том, что худший случай может произойти именно случайно, а не систематически из за особенностей поступающих данных.
Например, в конкретной системе входные данные могут быть отсортированными с большей вероятностью, чем $1\over n!$, даже если они поступают напрямую с какого-нибудь датчика, без обработки.