Временная и памятьная сложность (для данного кода):
- Среднее время: $\mathrm{O}(n\log n)$. Пояснение: каждый уровень рекурсии требует $\mathrm{O}(n)$ для разбиения, а в среднем глубина рекурсии $\mathrm{O}(\log n)$.
- Худшее время: $\mathrm{O}(n^2)$. Происходит при очень неравных разбиениях на каждом шаге (рекурсия глубиной $\mathrm{O}(n)$).
- Средняя дополнительная память (aux): $\mathrm{O}(n)$. Пояснение: на одном «уровне» суммарный объём временных списков порядка $n$, а глубина рекурсии обычно $\mathrm{O}(\log n)$, так что пиково активно порядка $O(n)$.
- Худшая дополнительная память: $\mathrm{O}(n^2)$. Для текущей реализации (создание новых списков left/right в каждом вызове) при сильно неравных разбиениях активные списки на стеке могут суммироваться до $n+(n-1)+\cdots =\mathrm{O}(n^2)$.
- Глубина рекурсии: в среднем $\mathrm{O}(\log n)$, в худшем случае $\mathrm{O}(n)$.
Входы, дающие $\mathrm{O}(n^2)$ для этой реализации (pivot = first element):
- уже отсортированный по возрастанию или по убыванию массив (например $[1,2,\dots ,n]$ или $[n,\dots ,1]$);
- массив с большим числом одинаковых элементов (например все элементы равны) — из-за условия $\le$ все равные попадут в один подмассив, что даёт крайне неравные разбиения.
Практические улучшения для устойчивости (избежание худших случаев и снижение памяти):
- Случайный выбор опорного элемента (randomized pivot): выбор случайного индекса перед разбиением даёт ожидаемую $\mathrm{O}(n\log n)$ для любых входов.
- Median-of-three (медиана из первого, среднего, последнего) — простая детерминированная эвристика, уменьшающая шанс плохого разбиения на почти-отсортированных данных.
- Ин-плейс partition (Lomuto или лучше Hoare) вместо создания новых списков — уменьшает дополнительную память до $\mathrm{O}(\log n)$ в среднем (только стек рекурсии).
- Трёхстороннее разбиение (Dutch National Flag) для обработки многих дубликатов: делит на и устраняет деградацию на массивах с одинаковыми ключами.
- Пороговое переключение на insertion sort для маленьких подмассивов (например при длине $\le 10$) — ускоряет на малых n и улучшает константы.
- Явная обработка глубокой рекурсии: сортировать большую часть итеративно и рекурсивно вызывать для меньшей (tail-recursion elimination), чтобы гарантировать стек $\mathrm{O}(\log n)$.
- Если нужна стабильность (сохранение относительного порядка равных элементов): либо использовать стабильный алгоритм (mergesort / Timsort), либо реализовать стабильную версию сортировки (обычно с дополнительной памятью).
Рекомендация: в практическом коде лучше либо использовать встроенную сортировку Python (Timsort — стабильна и с гарантией $\mathrm{O}(n\log n)$ в худшем случае), либо реализовать in-place randomized quicksort с трёхсторонним разбиением и порогом на insertion sort.