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

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

В этом случае рекурсия превращается в последовательное прохождение по массиву, что приводит к квадратичной сложности.

Однако в среднем и в лучшем случае быстрая сортировка работает за O(n log n), что делает её очень эффективной на практике.

Пример на C# (без оптимизаций выбора pivot):

void QuickSort(int[] arr, int left, int right) {
    if (left >= right) return;
    int pivot = arr[right];
    int partitionIndex = left;
    for (int i = left; i < right; i++) {
        if (arr[i] < pivot) {
            int temp = arr[i];
            arr[i] = arr[partitionIndex];
            arr[partitionIndex] = temp;
            partitionIndex++;
        }
    }
    arr[right] = arr[partitionIndex];
    arr[partitionIndex] = pivot;

    QuickSort(arr, left, partitionIndex - 1);
    QuickSort(arr, partitionIndex + 1, right);
}

Если входные данные уже отсортированы или почти отсортированы, и pivot выбирается плохо (например, всегда последний элемент), то сложность будет O(n²).

Какова временная сложность алгоритма быстрой сортировки при наихудшем сценарии?