Нашли ошибку?

Опорный из середины

СредняяОценка сложностиГлава 4
Нашли ошибку?

#быстрая сортировка#средний и худший случай#O-большоеid: ga-sorted-input-complexity

Быстрая сортировка выбирает опорным средний элемент. На вход подают уже упорядоченный список длины n. Определите время выполнения на таком входе.

Код

def quicksort(items: list[int]) -> list[int]:
    if len(items) < 2:
        return items
    mid = len(items) // 2
    pivot = items[mid]
    rest = items[:mid] + items[mid + 1:]
    less = [x for x in rest if x <= pivot]
    greater = [x for x in rest if x > pivot]
    return quicksort(less) + [pivot] + quicksort(greater)

Какое время выполнения?