Timsort

Merge sort (2.2.1.5) всегда делит массив пополам вслепую, независимо от содержимого. Timsort вместо этого сначала сканирует массив и находит runs — максимальные подряд идущие участки, уже отсортированные по возрастанию или по убыванию (убывающие переворачиваются за O(длина run) — тоже дёшево). Реальные данные (частично отсортированные логи, объединённые источники, повторные вставки в почти готовую структуру) почти всегда содержат длинные runs — и чем они длиннее, тем меньше слияний нужно сделать, тем ближе итоговое время к O(n).Merge sort (2.2.1.5) always splits the array blindly in half, regardless of content. Timsort instead first scans the array and finds runs — maximal contiguous stretches already sorted ascending or descending (descending ones get reversed in O(run length) — also cheap). Real-world data (partially sorted logs, merged sources, repeated inserts into an already-mostly-built structure) almost always contains long runs — and the longer they are, the fewer merges are needed, and the closer the total time gets to O(n).

Если run короче некоторого минимума (в реализации CPython — обычно 32-64 элемента, в зависимости от размера массива), его дополняют элементами и досортировывают insertion sort'ом (2.2.1.1) до минимальной длины — на таком маленьком масштабе insertion sort быстрее, чем создание отдельного крошечного run для слияния. Затем найденные runs сливаются попарно тем же алгоритмом слияния, что и в merge sort, с эвристикой galloping mode: если один run стабильно "проигрывает" много элементов подряд другому, слияние временно переключается на бинарный поиск позиции вставки вместо поэлементного сравнения.If a run is shorter than some minimum (in CPython's implementation, usually 32-64 elements depending on array size), it's padded with more elements and sorted up to that length with insertion sort (2.2.1.1) — at that small a scale, insertion sort is faster than creating a separate tiny run to merge. The found runs are then merged pairwise with the same merge algorithm as merge sort, with a galloping mode heuristic: if one run consistently "loses" many elements in a row to the other, the merge temporarily switches to a binary search for the insertion point instead of element-by-element comparison.

Здесь минимальная длина run — 4 элемента (вместо 32-64 у настоящего CPython, чтобы эффект был виден на маленьком массиве). Фаза 1 — найти естественные runs (зелёный — возрастающий, оранжевый — убывающий с разворотом, фиолетовый — короткий run, дополненный insertion sort'ом до минимальной длины). Фаза 2 — слить найденные runs попарно, слева направо, тем же алгоритмом слияния, что в merge sort.Here the minimum run length is 4 elements (instead of CPython's real 32-64, so the effect is visible on a small array). Phase 1 — find natural runs (green — ascending, orange — descending with a reversal, purple — a short run padded up to the minimum length with insertion sort). Phase 2 — merge the found runs pairwise, left to right, with the same merge algorithm as merge sort.