Здравствуйте, Буравчик, Вы писали:

Б>Это устраняет проблему выбора первого элемента — как и в оригинале теперь выбирается средний элемент. Сложность алгоритма остается та же O(N*logN)
Обычно, когда говорят о сложности, то говорят о сложности в худшем случае. У любого quicksort сложность в худшем случае не O(N * logN).