Какая сложность возникнет при передаче отсортированного массива в QuickSort

В QuickSort передача уже отсортированного массива приводит к худшему случаю — O(n²), так как опорный элемент (pivot) будет крайним (минимальным или максимальным), что вызовет несбалансированное разбиение. Каждая рекурсия обработает подмассив размером n-1, а не n/2.

Решение:
Выбирать pivot случайно или медиану из трёх элементов.

int partition(int[] arr, int low, int high) {
    // Выбор медианы из первого, среднего и последнего элемента
    int mid = low + (high - low) / 2;
    int pivot = medianOfThree(arr[low], arr[mid], arr[high]);
    // ... остальная логика разбиения
}

Такой подход снижает вероятность худшего случая.