Оценка эффективности быстрой сортировки

Опорный элемент делит последовательность в идеале почти пополам. Каждый из образовавшихся подпоследовательностей данного уровня иерархии рекурсивного вызова применяется тот же самый алгоритм так, в сумме по последовательностям quicksort обеспечивает встречное движение, а точнее всех переменных. Если последовательность упорядочена в обратном порядке, то опорный элемент, занимается крайнее левое или правое положение разбивает, обеспечивая максимальное количество число уровней глубины рекурсии n - 1, на каждом уровне просматривая N элементов. Таким образом, худшая оценка достигается в случае упорядоченности в подпоследовательности данных. Все алгоритмы по улучшению данных алгоритма Хоару сводится к выбору специальным образом опорного элемента так, чтобы разбиение по возможности происходило на середине отрезка.

Популярен алгоритм, в котором индекс опорного элемента получил название pivot.

Pivot:=(right-left) / 2 + left;

Все сравнения вида while k[i] > k[[j] à k[pivot]>k[i]

à k[pivot] < k[j];