Корректность (кратко)
- База: если $|a|\le 1$, возвращается отсортированный массив.
- Индукция: пусть для всех массивов длины < $n$ алгоритм возвращает отсортированный массив. Для массива длины $n$: выбирается опорный элемент pivot; все элементы разбиваются на left ( pivot). По индукции quicksort(left) и quicksort(right) дают отсортированные блоки; их конкатенация $\text{quicksort(left)}+[pivot]+\text{quicksort(right)}$ даёт весь массив в неубывающем порядке. Таким образом алгоритм корректен.
Временная сложность
- Лучший случай: при идеальных (балансных) разбиениях на каждом уровне => $T(n)=2T(n/2)+\Theta (n)$ → $T(n)=\Theta (n\log n)$.
- Средний случай (при случайном порядке/частых хороших разбиениях): ожидаемое время $\Theta (n\log n)$.
- Худший случай: при сильно несбалансированных разбиениях (напр., массив уже отсортирован и pivot всегда первый) => $T(n)=T(n-1)+\Theta (n)$ → $T(n)=\Theta (n^2)$.
Пространственная сложность (данная реализация)
- Доп. память для временных списков left/right на каждом вызове делает алгоритм не in‑place. Пиковая дополнительная память обычно $\Theta (n)$ (в среднем) плюс стек рекурсии глубины $\Theta (\log n)$ в среднем.
- В худшем случае глубина рекурсии $\Theta (n)$, и дополнительная память (из‑за стеков и временных списков) тоже может быть $\Theta (n)$ (и даже больше при одновременном существовании нескольких больших списков в процессе конкатенаций).
Другие свойства и проблемы
- Неустойчивость: текущая реализация не гарантирует сохранение исходного порядка равных элементов (pivot перемещается).
- На больших данных: риск переполнения стека (RecursionError) при глубокой рекурсии; худший случай $O(n^2)$ времени; высокий расход памяти из‑за копирования подсписков.
- В многопоточной среде в CPython чистые потоки не ускорят CPU‑bound задачу из‑за GIL — лучше multiprocessing или реализация на C. Параллельные рекуррентные вызовы возможны, но увеличивают расход памяти и накладные расходы на создание потоков/процессов.
Варианты улучшений
1. Рандомизация pivot:
- Выбирать pivot случайно (swap с первым или брать случайный индекс): резко снижает вероятность худшего случая; ожидаемое время остаётся $\Theta (n\log n)$, а вероятность $O(n^2)$ становится крайне малой.
2. Median‑of‑three:
- Выбирать pivot как медиану из трёх (первый, средний, последний) — простая эвристика против уже отсортированных входов.
3. 3‑way partition (Дейкстра) для большого числа равных элементов:
- Разбиение на pivot. Для множества повторяющихся ключей даёт существенное ускорение и устраняет деградацию.
4. In‑place partition (Hoare или Lomuto):
- Реализовать partition in‑place: уменьшает дополнительную память до $O(\log n)$ (рекурс. стек) в среднем. Пример: Hoare partition + рекурсивные вызовы на индексах.
5. Итеративная реализация / явный стек:
- Уменьшает риск переполнения системного стека и даёт возможность контролировать порядок обработки (обрабатывать меньший кусок первым — чтобы глубина стека была $O(\log n)$).
6. Introsort:
- Комбинация quicksort + heap sort: при превышении предельной глубины рекурсии (например, $2\lfloor \log n\rfloor$) переключаться на heapsort => гарантированный худший случай $O(n\log n)$.
7. Микро‑оптимизация для малых подмассивов:
- Для небольших подмассивов (например, длина < 16) использовать insertion sort — быстрее на коротких массивах.
8. Использовать готовые средства:
- В Python применять built‑in sorted()/list.sort() (Timsort) — адаптивный, стабильный, гарантированный $O(n\log n)$, экономичен по памяти для реальной работы.
9. Для данных, не помещающихся в RAM:
- Использовать внешнюю сортировку (external merge sort) или внешнюю версию quicksort с буферами/страничной обработкой.
10. Параллелизация:
- Для реального ускорения в Python: multiprocessing (процессы), либо реализовать в C/NumPy/numba, либо использовать библиотеки, которые освобождают GIL. При параллелизации следить за расходом памяти (каждый процесс/поток может копировать данные). Для in‑place параллельной сортировки — работать с общей памятью (например, mmap или shared memory) и разделять диапазоны без синхронизации.
Краткие практические рекомендации
- Для большинства задач в Python используйте built‑in sort.
- Если всё же нужна реализация quicksort: добавьте случайный выбор pivot или median‑of‑three, 3‑way partition, in‑place partition и порог на insertion sort; при опасении худшего случая — introsort. Для параллельной обработки больших объёмов — multiprocessing или специализированные C/C++ реализации / внешняя сортировка.