Ошибка. В приведённом коде элементы, равные опорному, отбрасываются: вы берёте только $[x:x<pivot]$, $[x:x>pivot]$ и добавляете один $[pivot]$, поэтому все остальные равные элементы теряются. Пример: на входе $a=[2,2,2]$ алгоритм вернёт $[2]$ вместо $[2,2,2]$ — то есть алгоритм некорректен (меняет мультимножество элементов).
Влияние:
- Корректность: нарушена — элементы с значением $==pivot$ удаляются.
- Сложность: попытка «пофиксить» заменой на $<=$ / $>=$ приведёт к проблеме бесконечной рекурсии/крайней неэффективности при всех равных элементах (например, если все элементы равны, рекурсия не уменьшается). Традиционная быстрая сортировка с некорректной обработкой равных может деградировать до худшего случая $O(n^2)$.
Правильный и эффективный фикс — трёхсторонняя (3-way) партияция: разбить на «меньше», «равно», «больше» и рекурсивно сортировать только меньшую и большую части. Тогда дубликаты сохраняются и при множестве равных элементов алгоритм работает эффективно (при всех равных — линейно). Исправленный код:
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)
Комплексность:
- В среднем: $O(n\log n)$.
- Худший случай (плохой выбор опорного): $O(n^2)$ (как и у обычного quicksort).
- При многих одинаковых элементах три‑частная партияция обычно даёт гораздо лучшее поведение; при всех элементах равных — $O(n)$.
Рекомендации: оставить 3‑way партицию и по возможности выбирать опорный элемент случайно или медиану трёх, чтобы снизить вероятность худшего случая.