SRT Поиск и сортировка Алгоритм
Timsort
Также: Тимсорт · сортировка Тима Петерса · natural merge sort · естественная сортировка слиянием · powersort · галоп · galloping mode · minrun
Сортировка, которой Python и Java упорядочивают списки: она ищет в данных уже упорядоченные куски и сливает их, а не сортирует всё заново. Внутри — стек серий с правилом, которое в 2015 году оказалось неверным, галоп вместо поэлементного слияния и с Python 3.11 — правило слияний powersort. Время коммитов этого сайта Timsort сортирует в 2,7 раза меньшим числом сравнений, чем обычная сортировка слиянием.
Время коммитов этого сайта, выписанное в порядке истории, почти упорядочено: 1258 чисел, и всего 19 кусков, внутри которых время только растёт. Беспорядок возникает там, где история сходится после работы в отдельных линиях. Обычной сортировке слиянием это всё равно: она режет массив пополам до самого конца и сливает обратно. Timsort сначала находит готовые куски, а потом сливает только их. Ниже — как он это делает, шаг за шагом.
На коммитах Timsort кладёт на стек 15 серий и сортирует за 2403 сравнения. Сортировка слиянием сверху вниз тратит на те же числа 6605, а n log₂ n для них — около 12 950. Переключите на случайные числа: там готовых кусков нет, и Timsort делает 19 660 сравнений против 19 436 у обычной сортировки слиянием, то есть чуть больше. Его выигрыш — не в лучшем слиянии, а в том, что на настоящих данных сливать почти нечего.
Идея
Настоящие данные редко бывают случайными: в них есть возрастающие куски — журналы, склеенные из отсортированных частей, списки, в конец которых дописали новое, таблицы, отсортированные по соседнему полю. Timsort проходит массив один раз и нарезает его на серии — куски, которые уже упорядочены, — и сливает их попарно, как сортировка слиянием. Чтобы слияния были дешёвыми, он держит серии на стеке и следит, чтобы сливались куски примерно одной длины, а когда одна сторона слияния выигрывает много раз подряд, переходит на прыжки.
История алгоритма — как Тим Петерс написал его для Python в 2002 году и как его потом перенесли в Java — рассказана в главе курса, вместе с короткой версией на Python. Здесь — то, что внутри: как устроены серии, почему порядок слияний важен, как в нём нашли ошибку и чем его заменили, и что такое галоп.
Серии и minrun
Серия — самый длинный кусок с текущего места, который либо не убывает, либо строго убывает. Убывающую серию Timsort разворачивает на месте. Строго — потому что при развороте равные элементы поменялись бы местами, а Timsort устойчив: равные элементы выходят в том же порядке, в каком пришли. Отсюда первая задача статьи.
Короткие серии — плохие кандидаты для слияния: на случайных данных серии длиной в два-три элемента, и сливать их — то же самое, что сортировать слиянием с нуля. Поэтому серию короче minrun Timsort удлиняет до minrun, вставляя следующие элементы вставками; место для каждого ищет двоичный поиск. Для коротких кусков вставки быстрее слияний: в них мало перемещений и всё лежит рядом в памяти.
Само minrun выбрано хитро. В CPython до версии 3.14 из длины массива n берутся старшие шесть бит, и к ним прибавляется единица, если среди отброшенных была хоть одна единица. Получается число от 32 до 64, при котором n/minrun — степень двойки или чуть меньше: на случайных данных все серии выходят длиной minrun, их число близко к степени двойки, и слияния до самого конца идут ровными парами. Для 1258 коммитов minrun = 40, для 1776 тестов — 56. В 2025 году Стефан Похман придумал правило лучше: длина серии чуть меняется от серии к серии, так что серий ровно степень двойки, а сливаемые серии отличаются по длине не больше чем на единицу. Оно вошло в CPython в версию, следующую за 3.14.
Стек серий
Порядок слияний важен. Слить кусок длиной x с куском длиной y стоит x + y: столько элементов придётся переложить. Если сливать длинную серию с короткими по одной, длинную будут перекладывать снова и снова, и сортировка станет квадратичной. Хорошо, когда сливаются серии примерно одной длины, — как в сортировке слиянием сверху вниз, где куски всегда равны.
Timsort не знает заранее, какие серии встретятся дальше, поэтому решает на ходу. Найденная серия кладётся на стек, и, пока верхние серии нарушают правило, их сливают. Правило Петерса похоже на числа Фибоначчи: каждая серия на стеке длиннее двух следующих над ней вместе, C > B + A, и длиннее одной следующей, B > A.
Если правило выполнено для всего стека, то стек из h серий над массивом длины n не выше logφ(n + 1), где φ ≈ 1,618 — золотое сечение.
Пусть x1 — длина верхней серии, x2 — следующей и так далее. Все длины целые и положительные, поэтому из x2 > x1 следует x2 ≥ x1 + 1, а из xk > xk−1 + xk−2 — что xk + 1 ≥ (xk−1 + 1) + (xk−2 + 1). Значит, числа yk = xk + 1 растут не медленнее чисел Фибоначчи: y1 ≥ 2 = F3, y2 ≥ 3 = F4, и по индукции yk ≥ Fk+2. Нижняя серия не длиннее массива, поэтому n + 1 ≥ Fh+2 ≥ φh — последнее неравенство для чисел Фибоначчи проверяется той же индукцией, потому что φ2 = φ + 1. Отсюда h ≤ logφ(n + 1).
Невысокий стек — это не только мало памяти. Правило гарантирует, что каждая серия, лёжа на стеке, длиннее всего, что над ней, и сливается с соседом не сильно короче себя, а значит, каждый элемент перекладывается O(log n) раз.
Ошибка, найденная доказательством
В 2002 году Петерс проверял правило только для трёх верхних серий: если C ≤ B + A, сливать. Казалось, этого хватит — ниже правило ведь уже выполнялось. В 2015 году Стейн де Гау с соавторами попробовали формально доказать правильность Timsort в Java с помощью программы проверки доказательств KeY, и доказательство не сошлось. Вот серии, на которых это видно:
Пока приходят 120, 80, 25 и 20, правило держится. Приходит 30: тройка 25, 20, 30 его нарушает, 25 и 20 сливаются в 45, и стек становится 120, 80, 45, 30. Верхняя тройка 80, 45, 30 теперь в порядке, проверка 2002 года останавливается — а ниже 120 ≤ 80 + 45. Правило нарушено там, куда проверка больше не смотрит. На специально построенных входах такие нарушения копятся, стек растёт выше расчётного, и в Java сортировка падала с выходом за границу массива, отведённого под стек. Исправление — смотреть ещё на одну серию ниже: условие D ≤ C + B тоже вызывает слияние. Его проверили тем же KeY, и в Python оно появилось в том же 2015 году. Вторая задача статьи — посчитать, во что обходятся слияния при исправленном правиле.
Powersort
У правила длин есть недостаток посерьёзнее ошибки: оно смотрит только на верх стека и может выбрать неудачный порядок слияний. В 2018 году Иэн Манро и Себастьян Вильд предложили powersort: решать не по длинам серий, а по их положению в массиве. Представим идеально сбалансированное двоичное дерево над всем массивом: корень делит его пополам, его дети — четвертинки, и так далее. Каждая граница между соседними сериями получает силу — глубину, на которой это дерево впервые разделяет середины двух серий. Граница с малой силой близка к корню, по ней сливать надо в самом конце; граница с большой силой глубоко, по ней можно сливать сразу. Правило: пока у границы под верхней серией сила больше, чем у только что найденной, сливать.
Манро и Вильд доказали, что цена слияний у powersort превышает наименьшую возможную для тех же серий не больше чем на слагаемое порядка n. С версии 3.11 CPython сливает серии по powersort; остальной Timsort — серии, minrun, галоп — остался прежним. На коммитах сайта разница видна сразу: по правилу 2015 года слияния стоят 5396 перекладываний, по powersort — 4534, на 16 % меньше. На случайных данных и на времени тестов, где все серии одной длины minrun, оба правила сливают одинаково, и цена совпадает.
Галоп
Само слияние двух серий тоже приспосабливается к данным. Обычное слияние сравнивает голову одной серии с головой другой и забирает меньшую — одно сравнение на элемент. Но в настоящих данных серии часто чередуются кусками: история основной линии и история рабочей ветки идут то одна, то другая. Если одна сторона выиграла семь раз подряд, Timsort переходит в галоп: место головы другой серии ищет прыжками — на 1, 2, 4, 8… элементов вперёд, а найдя отрезок, где она лежит, — двоичным поиском. Кусок из k элементов перекладывается целиком примерно за 2·log₂ k сравнений вместо k.
Слить 129 коммитов основной линии и 49 коммитов одной рабочей линии по одному стоит 173 сравнения, с галопом — 124. Галоп не бесплатен: если куски короткие, прыжки тратят больше, чем экономят. Поэтому порог входа min_gallop подстраивается: пока галоп окупается, порог снижается, и следующий вход наступает раньше, а когда не окупается — повышается. Перед слиянием Timsort вдобавок галопом ищет, сколько элементов в начале первой серии меньше всей второй и сколько в конце второй больше всей первой: они уже на своих местах, и их не трогают вовсе. На всей сортировке коммитов галоп сокращает число сравнений с 4281 до 2403.
Код
Листинг — Timsort целиком, с подсчётом сравнений и цены слияний: серии, minrun, вставки, стек по правилу 2002 года, 2015 года или powersort, галоп в слиянии и перед ним. Ради краткости слияние всегда копирует во временный массив первую серию; CPython копирует более короткую из двух и сливает с той стороны, откуда выгоднее, поэтому его числа сравнений немного другие. Демо разбирает minrun, серии 120, 80, 25, 20, 30 и сравнивает Timsort с обычной сортировкой слиянием на настоящих данных.
Время тестов каталога — данные другого рода: в них 626 естественных серий на 1776 чисел, почти все короче minrun = 56. Timsort удлиняет их вставками до 56 и дальше сливает 32 серии ровными парами: 15 174 сравнения против 16 511 у сортировки слиянием. Отсортированный и обратный массивы Timsort проходит за 1999 сравнений — одна серия, ни одного слияния.
Сколько это стоит
В худшем случае — O(n log n) сравнений, как у сортировки слиянием. На уже упорядоченных данных — n − 1 сравнение. Точнее, если в данных r серий, работа — O(n + n log r): слияния образуют дерево глубиной порядка log r. Память — временный массив под меньшую из сливаемых серий, то есть не больше половины n, и стек высотой O(log n).
Сравнения — не всё. Ниже время встроенной сортировки на трёх видах данных: случайные числа, 16 отсортированных кусков подряд — как 16 склеенных журналов — и отсортированный массив, в котором каждая сотая пара переставлена. В Python это Timsort, в Go — pdqsort, быстрая сортировка с защитой от плохих случаев, которая тоже замечает упорядоченные участки, но по-своему.
На 640 тысячах чисел Timsort в Python на 16 сериях быстрее, чем на случайных, в 2,8 раза, на почти упорядоченных — в 8,7 раза. pdqsort в Go тоже ускоряется — в 2,2 и 5,4 раза, — но готовые куски использует хуже: он не сливает их, а делит массив по опорному элементу. Go при этом быстрее Python на случайных числах и на сериях, а на почти упорядоченных до 160 тысяч чисел впереди Timsort. Там, где Go выигрывает, дело в том, как лежат данные: в Python каждое число — отдельный объект, и даже с особым быстрым сравнением для списков из одних чисел сортировка ходит по указателям, а Go сортирует сами числа, лежащие подряд.
Где работает
Python. list.sort и sorted — Timsort с версии 2.3, с 3.11 — с powersort. Устойчивость гарантирована документацией, и на ней держится приём «сортировать по нескольким ключам несколькими проходами»: сначала по второстепенному ключу, потом по главному.
Java. Arrays.sort и Collections.sort для объектов с Java 7 — это Timsort, перенесённый из Python; в документации так и написано. Массивы чисел сортируются другим алгоритмом, потому что для них устойчивость не нужна.
Браузеры. V8, движок JavaScript в Chrome, сортирует массивы Timsort с версии 7.0, вышедшей в 2018 году, — заодно сортировка в JavaScript стала устойчивой.
Данные, которые приходят кусками. Склеенные журналы, выгрузки по дням, список, в конец которого дописали немного нового, — всё это несколько длинных серий, и Timsort сливает их почти за линейное время. А замерять сортировку на уже упорядоченных данных надо с этим в голове: замер покажет линейное время, а не O(n log n).
История
Тим Петерс написал Timsort для Python 2.3 в 2002 году и подробно описал его в файле listsort.txt в исходниках CPython; галоп он взял из статьи Питера Макилроя 1993 года об оптимистичной сортировке. В 2009 году алгоритм перенесли в Java, и с Java 7 он сортирует объекты. В 2015 году Стейн де Гау, Юрриан Рот, Франк де Бур, Рихард Бубель и Райнер Хенле, пытаясь доказать его правильность, нашли ошибку в проверке стека; её исправили в Java и Python в том же году. В 2018 году Иэн Манро и Себастьян Вильд предложили powersort, он вошёл в Python 3.11, вышедший в 2022 году, а в 2025 году Стефан Похман предложил новое правило для minrun.
Задачи
Первая — повторить, как Timsort режет массив на серии: строгое убывание, minrun и удлинение. Вторая — посчитать цену всех слияний по правилу 2015 года и по powersort.
Серии Timsort Какие серии слитьДанные: Граф коммитов legost.in (git, до 16.10.2026) Время эталонных решений задач каталога на каждом тесте (замер в песочнице, 17.10.2026)