Timsort

Проблема

Сортировка слиянием даёт гарантию O(n log n), но игнорирует структуру реальных данных: логи, отсортированные по времени с редкими вставками, частично обработанные списки - всё это содержит длинные уже отсортированные участки. Сортировка вставками эффективна на маленьких и почти отсортированных массивах, но деградирует до O(n²) на больших случайных данных. Нужен алгоритм, который использует сильные стороны обоих подходов и адаптируется к реальному, а не худшему случаю.

Решение

Timsort идёт по массиву и сначала ищет естественный прогон - уже упорядоченный участок, который в реальных данных встречается сам по себе. Если участок убывает, он разворачивается за O(k) и становится возрастающим прогоном бесплатно. Если естественный прогон короче minrun (обычно 32-64 элемента), он достраивается сортировкой вставками до длины minrun - на таком размере она быстрее из-за низких констант. Отсортированные прогоны затем сливаются попарно тем же механизмом слияния, что и в merge sort, пока не останется один отсортированный массив. Чем длиннее естественные прогоны во входных данных, тем меньше слияний требуется.

Как это работает

Ключевая идея Timsort - не изобретение нового способа сравнивать элементы, а переиспользование структуры, которая уже есть во входных данных. Прежде чем что-либо сортировать, алгоритм сначала *ищет* прогоны: участки, которые уже возрастают или убывают. На массиве [1, 3, 5, 4, 2, 6, 8] первый прогон [1, 3, 5] находится за 2 сравнения, ничего не пересортировывая.

Убывающие прогоны не отбрасываются - они разворачиваются за O(k), где k - длина прогона, и становятся полноценными возрастающими прогонами. Это дёшево: разворот делает k/2 обменов, тогда как пересортировка вставками того же участка потребовала бы до k²/4 сравнений в худшем случае. На участке из 8 убывающих элементов это 4 обмена вместо потенциальных 16 сравнений.

Если естественный прогон короче minrun (в этой реализации фиксировано 32, в CPython вычисляется динамически через сдвиг битов длины массива так, чтобы n/minrun было близко к степени двойки), прогон достраивается сортировкой вставками до этой длины - не пересортировывается с нуля, а именно достраивается, потому что уже найденный префикс остаётся частью диапазона insertionSortRange.

Настоящий (CPython) Timsort сливает прогоны не парами подряд, а через стек с тремя инвариантами длины и режим галопирования (galloping): если один прогон стабильно "побеждает" другой много раз подряд, слияние переключается на бинарный поиск позиции вставки вместо поэлементного сравнения. Эта реализация упрощена до попарного слияния прогонов раундами без стека и без галопирования - она сохраняет и адаптивность (короткое число раундов при длинных естественных прогонах), и устойчивость, но не достигает точной производительности продакшен-версии на структурированных данных.

Проверка на реальных прогонах массива из 1000 элементов: уже отсортированный массив даёт 999 сравнений всего (одно на пару соседей при поиске единственного прогона на весь массив), тогда как n·log₂(n) ≈ 9966 - более чем в 9 раз меньше. Случайный массив из 1000 элементов даёт около 13700-14000 сравнений, что того же порядка, что и n·log₂(n), с некоторым запасом из-за O(n²) внутри блоков minrun.

Обычный merge sort не умеет использовать существующий порядок: он всегда делит массив пополам и сливает, независимо от того, отсортирован вход или нет, и всегда делает порядка n·log₂(n) сравнений. Timsort же на уже отсортированном массиве находит один прогон на весь массив и вообще не делает ни одного раунда слияния - это и есть разница между "гарантированная асимптотика" и "адаптивная асимптотика".

Timsort был написан Тимом Питерсом (Tim Peters) в 2002 году специально для CPython, заменив предыдущую реализацию сортировки на основе samplesort. Название буквально "Tim's sort" - редкий случай алгоритма, названного в честь конкретного инженера, а не абстрактного принципа, как у большинства классических сортировок.

Нюансы выбора

По сравнению с обычным merge sort: выбирайте Timsort, когда входные данные хотя бы иногда содержат порядок (логи, повторные сортировки почти тех же данных) - на полностью случайных данных выигрыш исчезает, и оба алгоритма делают сопоставимую работу.

По сравнению с quicksort: если нужна гарантия отсутствия O(n²) в худшем случае и устойчивость (сохранение порядка равных ключей), Timsort предпочтительнее - quicksort быстрее в среднем, но может деградировать и не устойчив без модификаций.

Когда сортировка выполняется многократно по разным ключам одного набора данных (например, сначала по дате, потом стабильно по статусу) - устойчивость гарантирует, что вторая сортировка не разрушит порядок, установленный первой.

Крайний случай - очень маленькие массивы (n < minrun): тогда Timsort вырождается в чистую сортировку вставками, без единого раунда слияния - для таких размеров можно с тем же результатом использовать insertion sort напрямую и не тянуть за собой сложность гибридной реализации.

Примеры в коде

CPython (Objects/listobject.c, функция listsort_impl) - оригинальная реализация Тима Питерса 2002 года для list.sort() и sorted(), до сих пор используется практически без изменений в логике прогонов.

OpenJDK портировал Timsort в java.util.Collections.sort() и Arrays.sort(Object[]) в 2009 году (JDK 7) - примитивные массивы (int[], double[]) при этом по-прежнему сортируются dual-pivot quicksort, потому что для них устойчивость не имеет смысла (нет "равных, но разных" объектов).

V8 (движок JavaScript в Chrome и Node.js) использует вариант Timsort для Array.prototype.sort() с 2018 года, заменив нестабильный quicksort - это устранило класс багов, где sort() менял порядок визуально одинаковых строк в UI.

Android использует Timsort в Collections.sort() через тот же код OpenJDK, что делает его одним из самых часто исполняемых алгоритмов сортировки в мире по числу устройств, где он фактически работает.

Когда применять

• Когда сортируются реальные данные, которые часто частично упорядочены (логи, истории изменений, повторные сортировки).
• Когда нужна и устойчивость, и хорошая производительность на типичных, а не только на худших входных данных.

Примеры из практики

• Python использует Timsort как реализацию встроенных sorted() и list.sort() с 2002 года.
• Java использует Timsort в Collections.sort() и Arrays.sort() для массивов объектов (не примитивов).