Какая алгоритмическая сложность быстрой сортировки

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

Ключевые факторы:

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

Пример кода:

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]  # опорный элемент (можно выбрать лучше)
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quicksort(left) + middle + quicksort(right)