sorted() и list.sort() в Python используют Timsort (Тим Питерс, 2002): гибрид сортировки слиянием и сортировки вставками, который использует порядок, уже имеющийся в данных. Он устойчив, в худшем случае O(n log n), а на отсортированном входе O(n). Сам API описан в уроке сортировка списков в Python.
Как устроен Timsort
- Run. Массив просматривается в поисках естественных участков: неубывающих или строго убывающих; убывающий участок разворачивается на месте.
- minrun. Короткие run продлеваются до
minrun(порядка 32–64 элементов) бинарными вставками, которые быстры на малых кусках. - Стек слияний. Run кладутся в стек и сливаются по правилам, сохраняющим сбалансированные размеры, поэтому дерево слияний имеет глубину
O(log n). - Галоп. Если при слиянии один run много раз подряд выигрывает сравнения, Timsort переходит к экспоненциальному поиску (галопу) и переносит целый кусок за раз.
В итоге сортировка устойчива и близка к n на почти отсортированных данных, а в остальных случаях к n log n. Рисунок выше — упрощённая модель.
