Timsort

Timsort

Timsort — гибридный алгоритм сортировки, сочетающий сортировку вставками и сортировку слиянием.

Данный алгоритм был изобретен в 2002 году Тимом Петерсом(в честь него и назван). В настоящее время Timsort является стандартным алгоритмом сортировки в Python, OpenJDK 7 и реализован в Android JDK 1.5. Чтобы понять почему — достаточно взглянуть на таблицу из Википедии:

Основная идея алгоритма

• По специальному алгоритму входной массив разделяется на подмассивы.

• Каждый подмассив сортируется сортировкой вставками или сортировкой выбором.

• Отсортированные подмассивы собираются в единый массив с помощью модифицированной сортировки слиянием.

Данный алгоритм основывается на том, что в реальном мире сортируемые массивы данных часто содержат в себе упорядоченные подмассивы. На таких данных Timsort существенно быстрее многих дргугих алгоритмов сортировки.

Алгоритм

Используемые понятия и комментарии

• [math]n[/math] — размер входного массива.

• [math]run[/math] — некоторый подмассив во входном массиве, который обязан быть упорядоченным одним из двух способов:

1. строго по убыванию [math] a_{i} \gt a_{i + 1} \gt ... [/math].
2. нестрого по возрастанию [math] a_{i} \le a_{i + 1} \le ... [/math].

• [math]minrun[/math] — минимальный размер подмассива, описанного в предыдущем пункте.

Алгоритм Timsort состоит из нескольких шагов:

Шаг №1. Вычисление minrun

Число [math]minrun[/math] определяется на основе [math] n [/math], исходя из принципов:

• Оно не должно быть слишком большим, поскольку к подмассиву размера [math] minrun [/math] будет в дальнейшем применена сортировка вставками, а она эффективна только на небольших массивах.

• Оно не должно быть слишком маленьким, так как чем меньше подмассив — тем больше итераций слияния подмассивов придётся выполнить на последнем шаге алгоритма. Оптимальная величина для [math] n / minrun [/math] — степень двойки. Это требование обусловлено тем, что алгоритм слияния подмассивов наиболее эффективно работает на подмассивах примерно равного размера.

• Согласно авторским экспериментам:

1. При [math] minrun \gt 256 [/math] нарушается пункт [math]1[/math].
2. При [math] minrun \lt 8 [/math] нарушается пункт [math]2[/math].
3. Наиболее эффективные значения [math] minrun [/math] из диапозона [math] (32; 65) [/math].
4. Исключение — если [math] n \lt 64 [/math], тогда [math] n = minrun [/math] и Timsort превращается в сортировку вставками.

Таким образом, алгоритм расчета [math] minrun [/math] не так уж сложен: берем старшие 6 бит числа [math] n [/math] и добавляем единицу, если в оставшихся младших битах есть хотя бы один ненулевой.

 int GetMinrun(int n) {
     int flag = 0;           /* станет 1 если среди сдвинутых битов есть хотя бы 1 ненулевой */
     while (n >= 64) {
         flag |= n & 1;
         n >>= 1;
     }
     return n + flag;
 }

Шаг №2. Разбиения на подмассивы и их сортировка

На данном этапе у нас есть входной массив, его размер [math]n[/math] и вычисленное число [math]minrun[/math]. Алгоритм работы этого шага:

1. Указатель текущего элемента ставится в начало входного массива.
2. Начиная с текущего элемента, идет поиск во входном массиве упорядоченного подмассива [math]run[/math]. По определению, в [math]run[/math] однозначно войдет текущий элемент и следующий за ним. Если получившийся подмассив упорядочен по убыванию — элементы переставляются так, чтобы они шли по возрастанию.
3. Если размер текущего [math]run[/math] меньше [math]minrun[/math], тогда выбираются следующие за найденным подмассивом [math]run[/math] элементы в количестве [math] minrun - size(run) [/math]. Таким образом, на выходе будет получен подмассив размером большим или равный [math]minrun[/math], часть которого (в лучшем случае — он весь) упорядочена.
4. К данному подмассиву применяем сортировка вставками. Так как размер подмассива невелик и часть его уже упорядочена — сортировка работает эффективно.
5. Указатель текущего элемента ставится на следующий за подмассивом элемент.
6. Если конец входного массива не достигнут — переход к пункту 2, иначе — конец данного шага.

Шаг №3. Слияние

Если данные изначального массива достаточно близки к случайным, то размер упорядоченных подмассивов близок к [math]minrun[/math]. Если в изначальных данных были упорядоченные диапазоны, то упорядоченные подмассивы могут иметь размер, превышающий [math]minrun[/math].

• Итак, нужно объединить полученные подмассивы для получения результирующего упорядоченного массива. Для достижения эффективности, объединение должно удовлетворять требованиям:

1. Объединять подмассивы примерно равного размера
2. Сохранить стабильность алгоритма (не делать бессмысленных перестановок).
   

Алгоритм шага №3:

1. Создается пустой стек пар <индекс начала подмассива> [math]-[/math] <размер подмассива>.
2. Берется первый упорядоченный подмассив.
3. Добавляется в стек пара данных <индекс начала текущего подмассива> [math]-[/math] <его размер>.
4. При выполнении двух последующих правил выполняется процедура слияния текущего подмассива с предыдущими.

Если [math]X, Y, Z[/math] — размеры трёх верхних подмассивов в стеке, то:

1. [math]X \gt Y + Z[/math]
2. [math]Y \gt Z[/math]

Если одно из правил нарушается — массив [math]Y[/math] сливается с меньшим из массивов [math]X[/math], [math]Z[/math]. Процедура повторяется до выполнения обоих правил или полного упорядочивания данных. Если остались не рассмотренные подмассивы, то берется следующий и переходим ко второму пункту. Иначе — конец.

Основная цель этой процедуры — сохранение баланса. Изменения будут выглядеть как на картинке, а значит и размеры подмассивов в стеке эффективны для дальнейшей сортировки слиянием.

Описание процедуры слияния

• Создается временный массив в размере меньшего из сливаемых подмассивов.

• Меньший из подмассивов копируется во временный массив, но надо учесть, что если меньший подмассив [math]-[/math] правый, то ответ (результат сливания) формируется справа налево. Дабы избежать данной путаницы, лучше копировать всегда левый подмассив во временный. На скорости это практически не отразится.

• Ставятся указатели текущей позиции на первые элементы большего и временного массива.

• На каждом шаге рассматривается значение текущих элементов в большем и временном массивах, берется меньший из них, копируется в новый

отсортированный массив. Указатель текущего элемента перемещается в массиве, из которого был взят элемент.

• Предыдущий пункт повторяется, пока один из массивов не закончится.

• Все элементы оставшегося массива добавляются в конец нового массива.

Модификация процедуры слияния подмассивов (Galloping Mode)

Рассмотрим процедуру слияния двух массивов:

[math]A = {1, 2, 3, ..., 9999, 10000}[/math]

[math]B = {20000, 20001, 20002, ..., 29999, 30000}[/math]

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

• Начинается процедура слияния.

• На каждой операции копирования элемента из временного или большего подмассива в результирующий запоминается, из какого именно подмассива был элемент.

• Если уже некоторое количество элементов (в данной реализации алгоритма это число равно 7) было взято из одного и того же массива — предполагается, что и дальше придётся брать данные из него. Чтобы подтвердить эту идею, алгоритм переходит в режим «галопа», то есть перемещается по массиву-претенденту на поставку следующей большой порции данных бинарным поиском (массив упорядочен) текущего элемента из второго соединяемого массива.

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

Для вышеописанных массивов [math] A, B [/math] алгоритм выглядит следующим образом: Первые 7 итераций сравниваются числа [math]1, 2, 3, 4, 5, 6, 7[/math] из массива [math]A[/math] с числом [math]20000[/math], так как [math]20000[/math] больше, то элементы массива [math]A[/math] копируются в результирующий. Начиная со следующей итерации алгоритм переходит в режим «галопа»: сравнивает с числом [math]20000[/math] последовательно элементы [math]8, 10, 14, 22, 38, 7+2^{i - 1}, ..., 10000 [/math] массива [math]A[/math]. ([math] \thicksim\log_{2}(n)[/math] сравнений). После того как конец массива [math]A[/math] достигнут и известно, что он весь меньше [math]B[/math], нужные данные из массива [math]A[/math] копируются в результирующий.

Доказательство времени работы алгоритма

Для оценки времени работы алгоритма Timsort составим рекуррентное соотношение. Пусть [math] T(n) [/math] — время сортировки массива длины n. Рассмотрим последнее слияние двух подмассивов [math] run1 [/math] и [math] run2 [/math]:

[math] T(n) = T(run1.size) + T(run2.size) + O(run1.size + run2.size) [/math]. Алгоритм построен таким образом, что сливаемые подмассивы имеют примерно равные размеры. Таким образом можно считать:

[math] T(n) = T(run1.size) + T(run2.size) + O(run1.size + run2.size) [/math] [math] \approx 2T(n/2) + O(n) \approx [/math] [math] 4T(n/4) + 2O(n) \approx \dots \approx 2^{k}T(1) + kO(n) [/math].

Осталось оценить [math]k[/math]. [math]n/minrun[/math] - количество сливаемых блоков, откуда следует, что [math]2^{k} = n/minrun[/math], значит [math] k = log(n/minrun)[/math].

[math]T(n) \approx 2^{k}T(1) + kO(n) [/math] = [math] log(n/minrun) + [/math][math]log(n/minrun)O(n)[/math] [math] = O(nlog(n)). [/math]

Источники

• Peter McIlroy "Optimistic Sorting and Information Theoretic Complexity", Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, ISBN 0-89871-313-7, Chapter 53, pp 467-474, January 1993.

• Magnus Lie Hetland Python Algorithms: Mastering Basic Algorithms in the Python Language. — Apress, 2010. — 336 с.

• Wikipedia - Timsort

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