Quali difficoltà possono sorgere durante l'elaborazione di un array già ordinato con l'algoritmo QuickSort?

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

Чтобы избежать этого, часто используют:

• Выбор случайного pivot (Randomized QuickSort).
• Метод медианы из трёх элементов (median-of-three).

Пример выбора pivot медианы из трёх:

int medianOfThree(int[] arr, int low, int high) {
    int mid = low + (high - low) / 2;
    int a = arr[low], b = arr[mid], c = arr[high];
    if ((a > b) != (a > c)) return low;
    else if ((b > a) != (b > c)) return mid;
    else return high;
}