Ошибки и замечания:
- В выражении `quicksort(left) + pivot + quicksort(right)` пытаются сложить список и скаляр — должно быть `+ [pivot]` или использовать список равных элементов.
- Алгоритм неустойчив (stable): сравнение `x >= pivot` помещает равные элементы в правую часть и нарушает исходный порядок.
- Выбор опорного элемента `pivot = a[0]` даёт худший случай $O(n^2)$ на уже отсортированных данных.
- Представленная версия не in-place — создаёт дополнительные списки (это нормально для функциональной реализации, но требует памяти).
Сложность:
- Средняя временная: $O(n\log n)$ - Худшая временная: $O(n^2)$ (при плохом выборе опоры)
- Дополнительная память: $O(n)$ (новые списки)
- Глубина рекурсии: в среднем $O(\log n)$, в худшем $O(n)$
Исправленная (простая) версия:
```python
def quicksort(a):
if len(a) <= 1:
return a
pivot = a[0]
left = [x for x in a[1:] if x < pivot]
right = [x for x in a[1:] if x >= pivot]
return quicksort(left) + [pivot] + quicksort(right)
```
Стабильная и более устойчивая (лучше выбрать случайную опору) версия:
```python
import random
def stable_quicksort(a):
if len(a) <= 1:
return a
pivot = a[random.randrange(len(a))] # уменьшает шанс худшего случая
left = [x for x in a if x < pivot]
equal = [x for x in a if x == pivot] # сохраняет порядок равных элементов
right = [x for x in a if x > pivot]
return stable_quicksort(left) + equal + stable_quicksort(right)
```
Пояснение к стабильной версии: разбиение на `left`, `equal`, `right` и использование списковых включений, которые проходят элементы в исходном порядке, сохраняют относительный порядок равных элементов (стабильность).