Timsort

TL;DR

Timsort — гибридная устойчивая сортировка, придуманная Тимом Петерсом в 2002 году для Python и ставшая стандартом в Java, Android и движках JavaScript. Идея: реальные данные почти всегда содержат уже упорядоченные серии (runs). Timsort находит их, короткие серии удлиняет до minrun (≈32–64) бинарной сортировкой вставками, а затем сливает runs по специальной политике, поддерживающей инвариант в духе чисел Фибоначчи. Это даёт: лучший случай [math]\displaystyle{ O(n) }[/math] (на почти отсортированных данных), средний и худший [math]\displaystyle{ O(n\log n) }[/math], устойчивость и адаптивность, ценой до [math]\displaystyle{ O(n) }[/math] дополнительной памяти под буфер слияния. Ускорение слияний даёт режим галопирования — вместо поэлементных сравнений копируются целые блоки после экспоненциального и бинарного поиска.

Свойство	Значение
Класс	Гибридная: сортировка вставками + слиянием; устойчивая
Автор	Тим Петерс (Tim Peters), 2002 (Python 2.3)
Лучший случай	[math]\displaystyle{ O(n) }[/math] (почти отсортированные данные)
Средний случай	[math]\displaystyle{ O(n\log n) }[/math]
Худший случай	[math]\displaystyle{ O(n\log n) }[/math]
Память	[math]\displaystyle{ O(n) }[/math] под буфер слияния (обычно [math]\displaystyle{ n/2 }[/math])
Устойчивость	да
Адаптивность	высокая (использует существующие runs)
Ключевые части	поиск runs, minrun + бинарные вставки, инвариант стека, галопирование
Где встречается	Python sorted, Java Arrays.sort(Object[]), Android, V8

Определения

Серия (run) — максимальная подряд идущая последовательность, упорядоченная по возрастанию (неубыванию) либо строго по убыванию. Естественный run — найденный во входе, а не созданный искусственно.

minrun — минимально допустимая длина run (обычно в диапазоне 32–64). Слишком короткие серии невыгодно сливать, поэтому их удлиняют до minrun.

Устойчивость (stability). Равные элементы сохраняют исходный взаимный порядок. Timsort устойчив: строго убывающий run разворачивается, а равные элементы «убывания» не образуют и не переворачиваются; при слиянии из двух равных выбирается левый.

Политика слияний (merge policy). Runs хранятся на стеке; после добавления нового run проверяется инвариант, и при его нарушении часть runs сливается. Инвариант: для верхних трёх runs [math]\displaystyle{ X, Y, Z }[/math] (снизу вверх) должны выполняться [math]\displaystyle{ Z \gt Y + X }[/math] и [math]\displaystyle{ Y \gt X }[/math].

Галопирование (galloping). Если при слиянии одна сторона выигрывает много раз подряд, вместо поэлементного сравнения выполняют экспоненциальный, затем бинарный поиск и копируют сразу блок.

Адаптивность — свойство алгоритма использовать уже существующий порядок: чем «упорядоченнее» вход, тем меньше работы.

Обозначения. [math]\displaystyle{ n }[/math] — длина массива; [math]\displaystyle{ r }[/math] — число runs; [math]\displaystyle{ X, Y, Z }[/math] — длины верхних runs на стеке; [math]\displaystyle{ \log }[/math] — двоичный. Под «run» ниже понимается возрастающая (неубывающая) серия.

Как выглядят runs и их нормализация, показано на рис. 1.

Рис. 1. Timsort находит максимальные возрастающие серии, а строго убывающие разворачивает.

Мотивация и интуиция

Классический mergesort не смотрит на вход: он всегда делит массив пополам и делает [math]\displaystyle{ n\log n }[/math] сравнений, даже если данные уже отсортированы. Быстрая сортировка работает на месте, но неустойчива и имеет худший случай [math]\displaystyle{ \Theta(n^2) }[/math]. На практике данные часто почти упорядочены (лог-файлы, результаты запросов, списки после частичного изменения), и это нужно эксплуатировать, не теряя гарантий.

Ключевая идея в одном абзаце: сначала найти уже упорядоченные серии, а затем слить их. Если вход отсортирован, получится один run и работа сведётся к линейному проходу; если данные случайны, runs короткие, но их длины выравниваются до minrun, а политика слияний гарантирует [math]\displaystyle{ O(n\log n) }[/math] в худшем случае. Устойчивость при этом сохраняется (см. рис. 2).

Рис. 2. Почти отсортированные данные — [math]\displaystyle{ O(n) }[/math]; случайные — [math]\displaystyle{ O(n\log n) }[/math]; гарантия худшего случая сохраняется.

Устройство

Алгоритм состоит из четырёх частей (см. рис. 3):

1. Поиск run. Идём от текущей позиции: если следующий элемент меньше — это строго убывающий run (его развернём), иначе — неубывающий. Пока порядок сохраняется, run растёт.
2. Удлинение до minrun. Если run короче minrun, к нему присоединяют элементы до min(minrun, n - lo) и сортируют весь отрезок бинарной сортировкой вставками.
3. Стек и политика. Готовый run кладётся на стек; mergeCollapse восстанавливает инвариант.
4. Финальный проход. forceCollapse сливает оставшиеся runs.

Рис. 3. Короткая серия удлиняется до minrun бинарными вставками; для малых [math]\displaystyle{ n }[/math] Timsort вырождается в сортировку вставками.

minrun и «магические» 32–64. Значение выбирается так, чтобы массив длиной [math]\displaystyle{ n }[/math] распадался на примерно равные runs, число которых — степень двойки (или близко к ней). Это делает последующие слияния сбалансированными. Точная функция (из кода CPython) сдвигает [math]\displaystyle{ n }[/math] вправо, пока не останется 6 бит, и «запоминает» любой потерянный младший бит.

Операции и алгоритмы

Операция: поиск и нормализация run

Идея. Найти максимальную серию от текущей позиции; строго убывающую — развернуть.

Пошаговое описание:

1. lo ← i; i ← i + 1.
2. Если a[i] < a[lo] — строго убывающий run: увеличивать i, пока строго убывает, затем развернуть отрезок.
3. Иначе — неубывающий run: увеличивать i, пока не убывает.
4. Вернуть длину i - lo.

Инвариант. a[lo..i-1] — неубывающая последовательность после нормализации.

Функция Find-Run(a, i)
Вход:  массив a; позиция i
Выход: длина найденного (нормализованного) run
Сложность: O(длины run)

1  lo ← i ; i ← i + 1
2  if i < n and a[i] < a[lo]                 # строго убывающий
3      while i < n and a[i] < a[i − 1]
4          i ← i + 1
5      Reverse(a, lo, i)
6  else
7      while i < n and not (a[i] < a[i − 1])  # неубывающий
8          i ← i + 1
9  return i − lo

Сложность. [math]\displaystyle{ O(\text{длина run}) }[/math].

Крайние случаи. Один элемент — run длины 1. Равные элементы образуют неубывающий run (не разворачиваются) — это и обеспечивает устойчивость.

Операция: удлинение run до minrun (бинарные вставки)

Идея. Довести короткий run до minrun, отсортировав отрезок бинарной сортировкой вставками.

Процедура Binary-Insertion-Sort(a, lo, hi)
Сложность: O(k log k) сравнений и O(k²) перемещений, k = hi − lo (мало)

1  for i ← lo + 1 to hi − 1
2      val ← a[i]
3      # двоичный поиск верхней границы: первый p, где val < a[p]
4      left ← lo ; right ← i
5      while left < right
6          mid ← left + ⌊(right − left) / 2⌋
7          if val < a[mid]: right ← mid else left ← mid + 1
8      for j ← i downto left + 1
9          a[j] ← a[j − 1]
10     a[left] ← val

Почему бинарный поиск. Число сравнений — [math]\displaystyle{ O(k\log k) }[/math], а сдвиг (перемещения) — [math]\displaystyle{ O(k^2) }[/math]; при [math]\displaystyle{ k \le 64 }[/math] это дёшево, зато устойчиво и просто. Верхняя граница (первый p с val < a[p]) сохраняет порядок равных.

Операция: политика слияний (инвариант стека)

Идея. Держать длины runs на стеке так, чтобы каждый нижний run был не короче суммы двух верхних. Нарушив инвариант — слить подходящую пару (см. рис. 4).

Инвариант. Для верхних [math]\displaystyle{ (X, Y, Z) }[/math]: [math]\displaystyle{ Y \gt X }[/math] и [math]\displaystyle{ Z \gt Y + X }[/math].

Процедура Merge-Collapse(stack)
Сложность: влияет только на порядок слияний; суммарно O(n log n)

1  while |stack| > 1
2      m ← |stack|
3      if m ≥ 3 and len[m−3] ≤ len[m−2] + len[m−1]
4          Merge-At(m−3)
5      else if m ≥ 4 and len[m−4] ≤ len[m−3] + len[m−2]
6          Merge-At(m−4)
7      else if len[m−2] ≤ len[m−1]
8          Merge-At(m−2)
9      else
10         break

Разбор. Если на стеке длины 10, 25, 40 (сверху 10), то [math]\displaystyle{ 10 \le 25 + 40 }[/math] — инвариант нарушен, сливаем (см. рис. 4).

Смысл. Инвариант заставляет длины runs расти хотя бы как числа Фибоначчи, поэтому их не больше [math]\displaystyle{ O(\log n) }[/math] и каждый элемент участвует в [math]\displaystyle{ O(\log n) }[/math] слияниях → [math]\displaystyle{ O(n\log n) }[/math].

Рис. 4. Инвариант «Z > Y + X, Y > X» даёт [math]\displaystyle{ O(\log n) }[/math] уровней и гарантию [math]\displaystyle{ O(n\log n) }[/math].

Операция: слияние и галопирование

Идея. Слить два соседних runs устойчиво, копируя в буфер меньший (для экономии памяти). Если одна сторона выигрывает 7 раз подряд — перейти в режим галопирования: найти бинарным поиском, сколько элементов другой стороны меньше текущего, и скопировать их блоком (см. рис. 5).

Процедура Merge-At(i)                      # сливаем runs i и i+1
Вход:  runs st[i], st[i+1] (соседние, оба возрастающие)
Выход: один объединённый run (устойчиво)

1  left ← копия a[base1..base1+len1)
2  li ← 0 ; j ← base2 ; k ← base1
3  wl ← 0 ; wr ← 0                          # серии «побед» сторон
4  while li < len1 and j < rightEnd
5      if a[j] < left[li]                   # правое строго меньше → берём правое
6          ++wr ; wl ← 0
7          if wr ≥ 7: Gallop-Right()        # копируем блок из правого
8          else a[k++] ← a[j++]
9      else                                 # левое ≤ правого → берём левое (устойчиво)
10         ++wl ; wr ← 0
11         if wl ≥ 7: Gallop-Left()         # копируем блок из левого
12         else a[k++] ← left[li++]
13 while li < len1: a[k++] ← left[li++]     # остаток правого уже на месте

Процедура Gallop-Right()
1  cnt ← число правых элементов < left[li]  # экспоненциальный + бинарный поиск
2  копировать cnt элементов из правого в выход

Процедура Gallop-Left()
1  cnt ← число левых элементов ≤ a[j]
2  копировать cnt элементов из буфера left в выход

Разбор. На рис. 5 правый run [5,9,12,17,40], левый элемент 18; после серии побед правого сторона галопирует: находит, что 5,9,12,17 < 18, и копирует их блоком.

Сложность. Слияние [math]\displaystyle{ O(len_1 + len_2) }[/math]; галопирование уменьшает число сравнений до [math]\displaystyle{ O(\log k) }[/math] на блок, что важно при дорогих сравнениях (объекты, строки).

Крайние случаи. Галопирование почти не включается на случайных данных и очень помогает на почти отсортированных. Копирование блока требует аккуратности с перекрытием областей.

Рис. 5. После 7 побед подряд — экспоненциальный и бинарный поиск, затем копирование целого блока.

Сводная таблица сложности

Операция	Время	Память
Поиск run	[math]\displaystyle{ O(\text{длина}) }[/math]	[math]\displaystyle{ O(1) }[/math]
Удлинение до minrun (бинарные вставки)	[math]\displaystyle{ O(k\log k) }[/math] сравнений	[math]\displaystyle{ O(1) }[/math]
Слияние двух runs	[math]\displaystyle{ O(\text{сумма длин}) }[/math]	[math]\displaystyle{ O(\min) }[/math] (буфер)
Весь Timsort, лучший случай	[math]\displaystyle{ O(n) }[/math]	[math]\displaystyle{ O(n) }[/math]
Весь Timsort, средний	[math]\displaystyle{ O(n\log n) }[/math]	[math]\displaystyle{ O(n) }[/math]
Весь Timsort, худший	[math]\displaystyle{ O(n\log n) }[/math]	[math]\displaystyle{ O(n) }[/math]

Оговорка: [math]\displaystyle{ O(n) }[/math] памяти — это буфер под меньший из сливаемых runs (до [math]\displaystyle{ n/2 }[/math]). Устойчивость и адаптивность — свойства по построению, а не «бонусы».

Трассировка примера

Массив a = [3, 5, 9, 8, 7, 4, 1, 2, 6, 10], положим minrun = 4 (для наглядности).

Шаг	Действие	Результат
1	Поиск run от 0: 3,5,9 растёт, 8 меньше → возрастающий run длины 3	run [3,5,9]
2	3 < minrun → удлиняем до 4, бинарные вставки по [3,5,9,8]	run [3,5,8,9]
3	Поиск run от 4: 7,4 — строго убывающий (длина 2) → разворот	run [4,7]
4	2 < minrun → удлиняем до 4, сортируем [4,7,1,2]	run [1,2,4,7]
5	Поиск run от 8: 6,10 — возрастающий	run [6,10]
6	2 < minrun → удлиняем (до конца)	run [6,10]
7	mergeCollapse сливает runs по инварианту	отсортировано
8	forceCollapse завершает	[1,2,3,4,5,6,7,8,9,10]

Проверьте устойчивость: равные элементы (если бы были) никогда не разворачиваются и при слиянии берётся левый. Трассировка сверена с реализацией из раздела «Служебное».

Корректность и оценка сложности

Устойчивость

Утверждение. Timsort устойчив.

Доказательство. (1) Поиск run разворачивает только строго убывающие серии, поэтому равные элементы сохраняют порядок. (2) Бинарные вставки используют верхнюю границу (первый p с val < a[p]), поэтому равный вставляется после равных. (3) При слиянии берётся левый элемент, когда left[li] ≤ a[j], то есть при равенстве левый идёт первым. Во всех трёх местах порядок равных сохраняется. [math]\displaystyle{ \square }[/math]

Корректность слияния и галопирования

Обычное слияние двух возрастающих runs даёт возрастающий run и сохраняет устойчивость (пункт 3 выше). Галопирование — лишь способ найти ту же границу, что и поэлементное сравнение: блок элементов правого run, строго меньших left[li], и блок левых элементов, не больших a[j], копируются в том же относительном порядке. Поэтому результат галопирующего слияния совпадает с обычным.

Гарантия $O(n\log n)$

Инвариант [math]\displaystyle{ Z \gt Y + X }[/math] и [math]\displaystyle{ Y \gt X }[/math] означает, что длины runs растут хотя бы как числа Фибоначчи. Отсюда:

• число runs на стеке [math]\displaystyle{ O(\log n) }[/math] (так как [math]\displaystyle{ F_k \ge \varphi^k }[/math]);
• каждый элемент участвует не более [math]\displaystyle{ O(\log n) }[/math] слияний;
• суммарное время слияний [math]\displaystyle{ O(n\log n) }[/math].

Важно: нарушение порядка в политике слияний (известная ранняя ошибка) приводит к вырождению до [math]\displaystyle{ O(n^2) }[/math]; корректная политика — не деталь, а часть доказательства оценки.

Адаптивность

Число runs [math]\displaystyle{ r }[/math] и их длины зависят от входа: уже отсортированный массив — один run ([math]\displaystyle{ O(n) }[/math]); строго обратный — один убывающий run и разворот ([math]\displaystyle{ O(n) }[/math]); почти отсортированный — несколько длинных runs и мало слияний.

Сравнение с альтернативами

Алгоритм	Лучший	Средний/худший	Память	Устойчив	Адаптивен
Timsort	[math]\displaystyle{ O(n) }[/math]	[math]\displaystyle{ O(n\log n) }[/math]	[math]\displaystyle{ O(n) }[/math]	да	высокая
Слиянием	[math]\displaystyle{ O(n\log n) }[/math]	[math]\displaystyle{ O(n\log n) }[/math]	[math]\displaystyle{ O(n) }[/math]	да	нет
Быстрая	[math]\displaystyle{ O(n\log n) }[/math]	[math]\displaystyle{ O(n\log n) }[/math] / [math]\displaystyle{ O(n^2) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	нет	слабая
Пирамидальная	[math]\displaystyle{ O(n\log n) }[/math]	[math]\displaystyle{ O(n\log n) }[/math]	[math]\displaystyle{ O(1) }[/math]	нет	слабая
Introsort	[math]\displaystyle{ O(n\log n) }[/math]	[math]\displaystyle{ O(n\log n) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	нет	слабая

Рис. 6. Timsort обменивает память на устойчивость, адаптивность и гарантию.

Вердикт. Нужна устойчивость + хорошее поведение на реальных данных — Timsort. Нужна минимальная память — Пирамидальная сортировка. Нужна максимальная скорость на случайных данных и допустима неустойчивость — Быстрая сортировка/introsort.

Где применяется

1. Python. list.sort() и sorted() используют Timsort с версии 2.3 (2002); устойчивость документирована как гарантия. Почему: списки объектов в скриптах часто почти упорядочены, а устойчивость ожидается при сортировке по составным ключам [1][2].

1. Java и Android. Arrays.sort(Object[]) и Collections.sort — Timsort с Java 7 (для примитивов — dual-pivot quicksort). Почему: объекты требуют устойчивости, примитивы — скорости [3].

1. Движки JavaScript. Спецификация Array.prototype.sort требует устойчивости; V8 и другие движки перешли на Timsort-подобные алгоритмы. Почему: контракт устойчивости и реальные частично сортированные массивы [4].

1. Rust и другие платформы. slice::sort — устойчивая сортировка; исторически Timsort- подобная, сейчас собственные алгоритмы (driftsort/ipnsort). Требование устойчивости сохраняется [5] ⚠️.

1. Обработка логов и потоков данных. Данные, поступающие частично упорядоченными (по времени, по ключу), сортируются быстрее именно из-за адаптивности Timsort [1][6].

Рис. 7. Timsort — сортировка по умолчанию многих платформ.

Историческая справка

Timsort придумал Тим Петерс (Tim Peters) в 2002 году для CPython; он вошёл в Python 2.3 вместо прежней реализации и с тех пор остаётся стандартной сортировкой Python [1][2]. Идея объединить сортировку вставками для малых отрезков и слияние для больших, с особой политикой слияний, восходит к анализам Р. Седжвика и к «натуральному» mergesort; Петерс формализовал политику на стеке и добавил галопирование.

В 2011 году Timsort был принят в Java 7 (Arrays.sort для объектов) [3]; позже — в движки JavaScript и в другие библиотеки. Известен и громкий инцидент: в 2015 году нашли, что при непротиворечивом, но нетранзитивном компараторе Timsort может выйти за границы массива (ошибка JDK-8072909) — напоминание, что контракт компаратора обязателен. Описание алгоритма и доказательство оценки [math]\displaystyle{ O(n\log n) }[/math] изложены в файле listsort.txt в исходниках CPython и в разборах сообщества [1][2][6].

Типичные ошибки и подводные камни

• Непротиворечивый, но нетранзитивный компаратор. Timsort (как и другие) может дать неверный результат или выйти за границы; компаратор должен быть строгим слабым порядком.
• Ожидание устойчивости при нестогом компараторе. Устойчивость гарантируется только для корректного «<».
• Нарушенная политика слияний. Неверный инвариант/порядок слияний вырождает алгоритм до [math]\displaystyle{ O(n^2) }[/math] — политика критична.
• Слишком маленький или большой minrun. Маленький — много слияний; большой — дорогая сортировка вставками. Разумно 32–64.
• Неверная обработка строго убывающих runs. Разворачивать нужно только строго убывающие; иначе устойчивость нарушится.
• Галопирование на случайных данных. Почти всегда выключено; ошибки в подсчёте блока ломают слияние (ищите в буфере left, а не в перезаписываемом массиве).
• Использование Timsort, когда нужна минимальная память. [math]\displaystyle{ O(n) }[/math] буфера — плата за устойчивость.
• Параллелизм. Классический Timsort последовательный; для параллельной сортировки берут другие схемы (parallel mergesort).
• Путаница адаптивности и «всегда [math]\displaystyle{ O(n) }[/math]». Линейное время — только для почти сортированных входов; случайные данные остаются [math]\displaystyle{ O(n\log n) }[/math].
• Сортировка по ключу без учёта стоимости сравнения. Галопирование помогает именно при дорогих сравнениях (объекты/строки), но не ускоряет дешёвые.

Задачи для практики

1. Поиск run. Реализуйте поиск неубывающих и строго убывающих runs с разворотом. Ограничение: устойчивость. Подсказка: равные не считаются убыванием.

1. minrun. Реализуйте функцию minrun (32–64) и объясните, почему диапазон именно такой. Подсказка: сбалансированность длин runs.

1. Бинарные вставки. Реализуйте Binary-Insertion-Sort с верхней границей; докажите устойчивость. Подсказка: первый p с val < a[p].

1. Инвариант стека. Для последовательности длин runs проверьте инвариант и определите, какие слияния нужно выполнить. Подсказка: [math]\displaystyle{ Z \gt Y + X }[/math], [math]\displaystyle{ Y \gt X }[/math].

1. Гарантия. Докажите, что инвариант даёт [math]\displaystyle{ O(\log n) }[/math] runs и [math]\displaystyle{ O(n\log n) }[/math] суммарно. Подсказка: числа Фибоначчи.

1. Галопирование. Реализуйте экспоненциальный и бинарный поиск блока и сравните число сравнений с поэлементным слиянием на почти отсортированных данных. Подсказка: порог 7.

1. Устойчивость на практике. Отсортируйте пары (ключ, индекс) и проверьте, что для равных ключей индексы возрастают. Подсказка: сравните со std::stable_sort.

1. Плохой компаратор. Покажите на примере, почему нетранзитивный компаратор ломает сортировку. Подсказка: a<b, b<c, но c<a.

Связанные темы

• Быстрая сортировка — неустойчивая, но быстрая на случайных данных.
• Сортировка слиянием — естественный предок Timsort (natural mergesort).
• Пирамидальная сортировка — гарантия [math]\displaystyle{ O(n\log n) }[/math] при [math]\displaystyle{ O(1) }[/math] памяти.
• Сортировки — обзор алгоритмов и нижняя граница [math]\displaystyle{ \Omega(n\log n) }[/math].
• Асимптотическая сложность — оценки и адаптивность.
• Дерево отрезков — другая структура «разделяй и властвуй».

Источники

1. Peters T. listsort.txt (описание Timsort в исходниках CPython). URL: https://github.com/python/cpython/blob/main/Objects/listsort.txt.
2. Документация Python: list.sort (гарантия устойчивости). URL: https://docs.python.org/3/library/stdtypes.html#list.sort.
3. OpenJDK: java.util.Arrays.sort, java.util.TimSort. URL: https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/Arrays.html.
4. Wikipedia: Timsort. URL: https://en.wikipedia.org/wiki/Timsort.
5. Документация Rust: slice::sort (устойчивость). URL: https://doc.rust-lang.org/std/primitive.slice.html#method.sort
6. Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. Introduction to Algorithms (CLRS). 3rd ed. — MIT Press, 2009. — Гл. 2 «Getting Started» (mergesort) и нижняя граница сортировок.