Выбор опорного элемента

Стратегии выбора pivot в QuickSort влияют на производительность: первый элемент (простой, O(n²) на отсортированном), последний, средний (middle index), медиана трёх (median-of-three: first, middle, last — лучше для частично отсортированных), случайный (randomized QuickSort, ожидаемое O(n log n) на любых данных). Худший случай O(n²) при неудачном выборе (все элементы меньше/больше pivot). Оптимальный pivot — медиана массива, но её поиск O(n) делает алгоритм медленнее