Что такое наихудший сценарий работы алгоритма QuickSort при сортировке?

Наихудший сценарий работы алгоритма QuickSort возникает, когда выбранный опорный элемент (pivot) всегда оказывается либо минимальным, либо максимальным элементом в текущем подмассиве. В этом случае разбиение массива происходит очень неравномерно: один подмассив содержит n-1 элемент, а другой — 0.

В результате глубина рекурсии становится равной n, и общее время работы алгоритма деградирует до квадратичной сложности — O(n²).

Пример: если массив уже отсортирован или отсортирован в обратном порядке, и опорный элемент выбирается, например, всегда первый или последний элемент, то QuickSort будет работать в худшем случае.