Код, который вы привели, — классическая «питоновская» реализация quicksort в функциональном стиле:

def quicksort$a$:
if len$a$ <= 1:
return a
pivot = a$$len(a)//2$$ left = [x for x in a if x < pivot]
middle = $$xforxinaifx==pivot$$ right = [x for x in a if x > pivot]
return quicksort$left$ + middle + quicksort$right$

1) Временная сложность

В среднем: O$nlogn$. При «хороших» разбиениях $обычноглубинарекурсии\approx O(logn)$ на каждом уровне делаем O$n$ сравнений, уровней ≈ O$logn$.В худшем случае: O$n^2$. Если опорный элемент постоянно даёт сильно несбалансированные разбиения $например,одинподмассивразмерn-1,другой0$, глубина ≈ n и суммарно ≈ 1+2+...+n сравнений → O$n^2$.

2) Память $auxiliary/peak$

Текущая реализация создаёт новые списки left/middle/right на каждом вызове:
В среднем $при«хороших»разбиениях$: пик занимаемой дополнительной памяти — O$n$. Более точный подсчёт: на уровнях рекурсии суммарно живые элементы дают геометрическую сумму n + n/2 + n/4 + ... = O$n$.В худшем случае $сильныйперекос$: пик может быть O$n^2$ $вызовысоздаютспискиразмеромn,n-1,n-2,...иониостаютсяживыминастеке$, то есть очень плохо по памяти.Рекурсивная глубина: в среднем O$logn$, в худшем O$n$ — это дополнительно стек вызовов.

3) Стабильность

Данная реализация стабильна. Разделение выполнено фильтрами, которые сохраняют порядок элементов, и при конкатенации относительный порядок равных элементов сохраняется. $Тоестьэлементысравнымизначенияминеменяютпорядокотносительнодругдруга.$

4) Практические улучшения и варианты

a) Выбор опорного элемента

Случайный pivot $random.choiceилиswapсrandomindex$ сильно уменьшает шанс худшего случая на «враждебных» входах → часто достаточное эмпирическое решение.median-of-three $например,median(a[low],a[mid],a[high])$ уменьшает шанс плохих разбиений на почти-отсортированных данных.Для жёстких гарантий — медиана медиан $median-of-medians$ даёт детерминированный O$n$ выбор опоры и гарантирует O$nlogn$ времени, но сложнее и в практике редко используется.

b) In-place варианты $меньшедополнительнойпамяти$

Классический in-place quicksort с разделением Ломуто или Хоара использует O$logn$ рекурсивной памяти в среднем и O$1$ дополнительной памяти для данных $безсозданияновыхсписков$. Минус: неустойчив.Пример $Hoare-партитция,итеративный/рекурсивныйвариант$:

def quicksort_inplace$a,lo=0,hi=None$:
if hi is None: hi = len$a$-1
while lo < hi:

median-of-three можно сюда вставить для a$$lo$$, a$$(lo+hi)//2$$, a$$hi$$ p = partition$a,lo,hi$ # реализуйте Hoare/Lomuto
# рикурсивно сортируем меньшую часть, итеративно — большую $tailrecursionelimination$ if p - lo < hi - p:
quicksort_inplace$a,lo,p-1$ lo = p+1
else:
quicksort_inplace$a,p+1,hi$ hi = p-1

$реализуйтеpartitionвстилеHoare/Lomuto;вHoare-партитцииp—индексразбиения.$

c) Трёх-путевая $DutchNationalFlag$ партиция

При большом количестве равных ключей обычный quicksort деградирует. 3-way разбиение $меньше=,равноpivot,больше=$ даёт O$n$ на массиве с большим числом дубликатов и в целом улучшает константы:

def quicksort_3way$a,lo=0,hi=None$:
if hi is None: hi = len$a$-1
if lo >= hi: return
lt, i, gt = lo, lo+1, hi
pivot = a$$lo$$ while i <= gt:
if a$$i$$ < pivot:
a$$lt$$, a$$i$$ = a$$i$$, a$$lt$$; lt += 1; i += 1
elif a$$i$$ > pivot:
a$$i$$, a$$gt$$ = a$$gt$$, a$$i$$; gt -= 1
else:
i += 1
quicksort_3way$a,lo,lt-1$ quicksort_3way$a,gt+1,hi$

d) Комбинация с insertion sort

Для маленьких подмассивов $обычнопорог10–40$ быстрее использовать insertion sort вместо рекурсии — уменьшает константы.

e) Избежать глубокой рекурсии

Применять tail recursion elimination $sortsmallerhalfрекурсивно,абольшуювцикле$, или использовать собственный стек, чтобы избежать переполнения стека при больших n.В Python глубокая рекурсия часто запрещена $лимит1000$, поэтому для больших n лучше in-place итеративный вариант или увеличить recursionlimit $нолучшенеполагатьсянаэто$.

f) Использовать встроенный сортировщик Python

Для практических задач в Python предпочтительнее использовать list.sort или sorted — это Timsort: стабильный, O$nlogn$ в худшем случае, хорош для частично отсортированных данных и обычно быстрее самописного quicksort.

5) Итог $кратко$

Ваш код: время среднее O$nlogn$, худшее O$n^2$; память средняя O$n$, худшая O$n^2$; стабильный.In-place quicksort: время те же, память средняя O$logn$ $рекурс.стек$, худшая O$n$; обычно нестабилен.Практические приёмы: случайный/median-of-three pivot, 3-way partition для дубликатов, использовать insertion sort для маленьких подмассивов, избегать глубокой рекурсии, или просто применять встроенный sorted/list.sort.

Если нужно, могу:

привести полный рабочий код in-place quicksort с Hoare-партитцией и median-of-three,или показать более подробный анализ памяти $peakliveallocations$ для разных сценариев.