Коротко — почему плохо, оценка худшего случая, и минимум три улучшения.
Почему плохо на массивах с одинаковыми элементами
- При всех элементах равных pivot = a[0] и в left попадают все остальные, right пуст. Рекурсия идёт по массиву размера $n-1$, затем $n-2$ и т.д., то есть глубина рекурсии $\Theta (n)$.
- Количество сравнений приближённо $\frac{n(n-1)}{2}=\Theta (n^2)$.
- Кроме того каждый уровень создаёт новые списки и копии при конкатенации — суммарные аллокации/копирования могут быть квадратичными, что сильно бьёт по производительности и памяти. Рекурсивная глубина может превысить лимит и привести к переполнению стека.
Худший случай (временная и пространственная сложность)
- Время: $O(n^2)$.
- Пиковая дополнительная память для чистой реализации с новыми списками и конкатенацией может вести себя как $O(n^2)$ суммарно и $O(n)$ пиково; при in-place реализации — дополнительная память (стек) в худшем случае $O(n)$, в среднем $O(\log n)$.
Предложения (минимум три), влияние на сложность и стабильность
1) Трёхчастная (3-way) партицияция (Dutch National Flag)
- Что: при одной проходке разделять на элементы « pivot» и рекурсировать только на «».
- Влияние на сложность: на массивах с множеством равных элементов даёт линейную или близкую к линейной работу (например, при всех элементах равных — один проход $O(n)$ и рекурсия не идёт). В общем худшем случае остаётся $O(n^2)$ при плохом выборе pivot, но вероятность плохого поведения для случайного pivot уменьшается.
- Память: можно сделать in-place — дополнительная память $O(\log n)$ стек в среднем.
- Стабильность: обычно нестабильна (элементы с равными ключами могут менять относительный порядок).
2) Случайный выбор опорного элемента или медиана из трёх (random pivot / median-of-three)
- Что: выбирать pivot случайно или как медиану первого/среднего/последнего для уменьшения шансов на вырожденный разрез.
- Влияние на сложность: делает ожидаемое время $O(n\log n)$ с высокой вероятностью; уменьшает шанс получить последовательную деградацию до $O(n^2)$. Не меняет худший теоретический предел $O(n^2)$, но практический риск очень мал.
- Память/стабильность: не влияют на стабильность (алгоритм остаётся нестабильным), не меняют асимптотику памяти.
3) In-place партиция (Hoare/Lomuto) и устранение лишних копий/конкатенаций
- Что: не строить новые списки через list comprehensions и не конкатенировать; работать с индексами в исходном массиве, менять элементы местами. Также применять хвостовую рекурсию (рекурсировать на меньшей части и цикл на большей), чтобы ограничить глубину стека.
- Влияние на сложность: время остаётся тем же в асимптотике, но реальная скорость и память значительно улучшаются; дополнительная память — $O(\log n)$ в среднем для стека, $O(n)$ в худшем. Меньше аллокаций — меньше констант.
- Стабильность: in-place partition всё ещё не стабилен.
4) Гибрид: при малых подмассивах переключаться на сортировку вставками
- Что: для подмассивов размера ≤ $k$ (например, $k=16$) не рекурсировать, а в конце дописать insertion sort для мелких участков.
- Влияние на сложность: не меняет асимптотику, но улучшает практическую производительность за счёт меньших констант и лучшего поведения для мелких n.
- Стабильность: insertion sort сама по себе стабильна; если интегрировать в нестабильный quicksort, итоговая сортировка останется нестабильной, если in-place перестановки изменяли порядок.
5) Использовать проверенные библиотеки / другой алгоритм: Timsort (как Python built-in sorted())
- Что: заменить свою реализацию на встроенный sorted() / list.sort(), который реализует Timsort.
- Влияние на сложность: гарантированное $O(n\log n)$ в худшем случае и оптимизации для почти отсортированных данных; стабильный. Практически всегда быстрее и экономнее по памяти/времени, чем простая реализация quicksort.
- Стабильность: Timsort — стабильный алгоритм.
Краткое резюме рекомендаций для практической реализации
- Для множества равных элементов: сразу применяйте 3-way партицию (существенно снижает работу).
- Выбирать pivot случайно или медиану трёх, делать партицию in-place и избегать конкатенаций/создания новых списков.
- Использовать гибрид с insertion sort для малых подмассивов.
- Если важна простота и стабильность — использовать built-in sorted() / list.sort().
Это минимально необходимые улучшения: 3-way partition + случайный/медианный pivot + in-place partition (плюс гибрид с insertion sort и/или использование встроенной сортировки) решают и проблему с одинаковыми элементами, и улучшают память/время на практике.