Код, который вы привели, — классическая «питоновская» реализация 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 = [x for x in a if x == pivot]
right = [x for x in a if x > pivot]
return quicksort(left) + middle + quicksort(right)

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

В среднем: O(n log n). При «хороших» разбиениях (обычно глубина рекурсии ≈ O(log n)) на каждом уровне делаем O(n) сравнений, уровней ≈ O(log n).В худшем случае: 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(log n), в худшем O(n) — это дополнительно стек вызовов.

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

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

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

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

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

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

Классический in-place quicksort с разделением Ломуто или Хоара использует O(log n) рекурсивной памяти в среднем и 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
# рикурсивно сортируем меньшую часть, итеративно — большую (tail recursion elimination)
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) Трёх-путевая (Dutch National Flag) партиция

При большом количестве равных ключей обычный 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 (sort smaller half рекурсивно, а большую в цикле), или использовать собственный стек, чтобы избежать переполнения стека при больших n.В Python глубокая рекурсия часто запрещена (лимит ~1000), поэтому для больших n лучше in-place итеративный вариант или увеличить recursionlimit (но лучше не полагаться на это).

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

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

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

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

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

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