Алгоритм сортировки Timsort

Автор: CoolPython

Для сортировки в CPython используется алгоритм Timsort, который его создатель Тим Петерс застенчиво назвал в честь себя. Timsort — это комбинация сортировки вставками и сортировки слиянием, заточенная под работу с реальными данными. Дело в том, что на практике массивы, которые нужно сортировать, часто бывают частично упорядочены и Timsort пользуется этим предположением для ускорения работы.

Логика работы Timsort на самом деле довольно прозрачная:

  • Timsort делит входной массив на подмассивы;
  • сортирует подмассивы вставками;
  • объединяет их попарно сортировкой слиянием;
  • и возвращает отсортированный массив.

Но дьявол кроется в деталях.

Делим на подмассивы

Части, на которые алгоритм делит входной массив, в описании алгоритма автор называет run’ами. Так на какое количество run’ов следует разделить входной массив? Здесь два соображения. Во-первых, части должны быть достаточно короткими, чтобы их было выгодно сортировать вставками. А еще мы хотим, чтобы пары последовательностей, которые позже поступят в сортировку слиянием, были примерно одинаковой длины. Дальше происходит магия, которая учитывает эти соображения и выбирает длину подпоследовательности minrun между 32 и 64 элементами. При этом если входной массив короче 64 элементов, то на части он не делится.

Сортируем run’ы

Перед тем, как приступить к сортировке подмассива, алгоритм ищет изначально упорядоченные участки. Если они слишком короткие и не дотягивают до минимального размера, то алгоритм удлинняет их бинарной сортировкой (http://www.geneffects.com/briarskin/theory/binary/index.html). Бинарная сортировка — это разновидность сортировки вставками, которая помещает элементы на свои места, используя двоичный поиск. Сортировки вставками как раз эффективны в случаях небольших частично упорядоченных массивов. Сам Петерс пишет, что это лучшее, что можно было выбрать, учитывая ограничения более утонченных алгоритмов.

Сливаем подмассивы

По мере того, как упорядоченные run’ы формируются, сортировкой слияния они объединяются попарно во всё более крупные отсортированные куски. При этом, если алгоритм при слиянии последовательностей встречает два участка вида

a = [1, 2, 3, 4]
b = [5, 6, 7, 8]

то по понятным причинам может объединить их быстрее, чем поэлементным перебором. Эта модификация сортировки называется galloping, поскольку в этом режиме алгоритм переносит на новое место не один элемент, а сразу несколько. Досортировки и слияния повторяются до тех пор, пока не достигается полная упорядоченность входного массива.

Вывод

Объем алгоритма в исходнике примерно 2к строк и, как можно догадаться по описанию, код довольно запутанный. Зато за счет использования упорядоченности в реальных данных сложность Timsort в лучшем случае линейная. В худшем случае, если входные данные случайные, timsort справится за O(n log n), а это неплохо для сортировки. Кстати, несмотря на то, что Timsort изначально был придуман в Python-сообществе, сейчас он используется еще в Java, Swift и Android platform.

Вот что нужно запомнить о Timsort:

  • Timsort это гибридный алгоритм сортировки, сочетающий модифицированные варианты сортировки вставками и сортировки слиянием;
  • Timsort пользуется тем, что реальные данные часто бывают частично упорядочены;
  • В лучшем случае сложность O(n), в худшем — O(n log n)).

Визуализацию работы алгоритма можно посмотреть здесь:

Видно, как сначала строятся run’ы и как они сливаются. Обратите внимание, что в обоих прогонах всегда объединяются примерно равные по размеру части