Коротко о причине, исправлениях и сложностях.
Причина ошибки
- Реализация рекурсивная, глубина рекурсии равна высоте рекурсивного дерева. В худшем (патологическом) раскладе высота может быть $O(n)$, и при больших $n$ превышается предел глубины рекурсии Python (RecursionError / стековое переполнение).
- Патология возникает, когда выбранный опорный элемент последовательно даёт очень неравные разбиения (одна часть почти весь массив, другая пустая). В вашем коде опорный элемент — элемент с индексом $len(a)//2$, который в редких входах может каждый раз оказаться экстремальным и вызвать цепочку глубиной $\Theta (n)$.
Что делать (варианты исправлений)
1. Случайный опорный элемент (простая и эффективная эврика):
- перед разбиением выбирать опорный случайно: `pivot = random.choice(a)` или `pivot = a[random.randrange(len(a))]`. Это робастно против анти-адверсариальных входов (ожидаемая глубина $O(\log n)$).
2. Гарантировать малую глубину стека — рекурсивно обрабатывать всегда меньшую часть, а для большей — цикл (tail recursion elimination):
- в каждой итерации рекурсировать только по меньшей части, для большей переходить в цикл; это ограничивает глубину стека $O(\log n)$ в среднем и в лучшем случае.
3. Итеративная реализация с явным стеком или in-place partition (Hoare/Lomuto):
- написать быструю сортировку in-place и использовать явный стек/цикл — уменьшает дополнительную память и контролирует глубину рекурсии.
4. Использовать готовую сортировку Python: `sorted(a)` или `a.sort()` (Timsort) — стабильная, гарантированно $O(n\log n)$ в худшем случае.
5. (Менее рекомендовано) Увеличить предел рекурсии: `sys.setrecursionlimit(...)` — временное решение, не устраняет алгоритмическую уязвимость.
Примеры (короткие)
- Случайный pivot:
```
import random
def quicksort(a):
if len(a) <= 1:
return a
pivot = random.choice(a)
left = [x for x in a if x < pivot]
mid = [x for x in a if x == pivot]
right= [x for x in a if x > pivot]
return quicksort(left) + mid + quicksort(right)
```
- Обработка меньшей части рекурсивно (уменьшение глубины стека):
```
def quicksort(a):
while len(a) > 1:
pivot = a[len(a)//2]
left = [x for x in a if x < pivot]
mid = [x for x in a if x == pivot]
right= [x for x in a if x > pivot]
if len(left) < len(right):
left = quicksort(left)
a = left + mid + right
return a
else:
right = quicksort(right)
a = left + mid + right
return a
return a
```
(лучше реализовать аккуратно — идея: рекурсировать по меньшей части и итеративно обрабатывать большую).
Оценка сложности
- Средняя (ожидаемая) временная сложность: $\Theta (n\log n)$.
- Худшая временная сложность (при постоянных очень неравных разбиениях): $\Theta (n^2)$.
- Память:
- Ваша текущая версия, создающая новые списки, требует дополнительной памяти $O(n)$ (плюс стек рекурсии).
- Глубина стека: в среднем $O(\log n)$, в худшем $O(n)$ (если не предпринимать мер, см. выше).
- In-place реализация может уменьшить дополнительную память до $O(1)$ (плюс стек).
Резюме
- Причина: возможные крайне неравные разбиения => глубина рекурсии $\Theta (n)$ и переполнение стека.
- Решения: выбирать случайный опорный элемент, рекурсировать по меньшей части (tail recursion elimination), делать in-place/итеративную реализацию или использовать встроенную сортировку. Ожидаемая сложность средняя $\Theta (n\log n)$, худшая $\Theta (n^2)$, глубина стека в худшем случае $\Theta (n)$.