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:

• Создается пустой стек пар <индекс начала подмассива> [math]-[/math] <размер подмассива>.
• Берется первый упорядоченный подмассив.
• Добавляется в стек пара данных <индекс начала текущего подмассива> [math]-[/math] <его размер>.
• Затем правило следующее. Пусть [math]X,Y,Z - [/math] длины верхних трех интервалов, которые лежат в стеке. Причем [math]X[/math] – это последний элемент стека.

1. Повторяем пока выражение ([math]Z \gt X + Y[/math] && [math]Y \gt X[/math]) не станет истинным
2. Если количество элементов в стеке не меньше 3 и [math]Z \leqslant X + Y[/math] – сливаем [math]Y[/math] c [math]min(X,Z)[/math]. Иначе Если [math]Y \leqslant X [/math] – сливаем [math]X[/math] c [math]Y[/math].
3. Возвращаемся в п.1.

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

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

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

• Меньший из подмассивов копируется во временный массив, но надо учесть, что если меньший подмассив [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] копируются в результирующий.

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

Главный факт, который нам понадобится для доказательства нужной оценки времени работы в [math]О(nlog(n))[/math] - это то, что сливаемые массивы всегда имеют примерно одинаковую длинну. То есть подмассивы [math]run_1[/math], [math]run_2[/math] такие, что [math]run_1.size \gg run_2.size[/math] будут слиты только тогда, когда размеры соответствующих подмассивов, в которые они войдут будут примерно равны. Например, если на вход подан массив [math]64, 32, 16, 8, 4, 2, 1[/math], то, временно забыв про понятие [math]minrun[/math], Timsort сделает следующие слияния:

1. 64, 32, 16, 8, 4, 2, 1, 1
2. 64, 32, 16, 8, 4, 2, 2
3. 64, 32, 16, 8, 4, 4
4. 64, 32, 16, 8, 8
5. 64, 32, 16, 16
6. 64, 32, 32
7. 64, 64
8. 128

При сливании двух подмассивов [math]run_1[/math],[math]run_2[/math] будет произведенно [math]O(run_1.size + run_2.size)[/math] операций сравнения. Результирующий подмассив [math]run_{12}[/math] будет удовлетворять выражению [math]run_{12}.size \approx 2run_1.size \approx 2run_2.size [/math]. Таким образом, каждый подмассив [math]run_i[/math] может поучаствовать в не более [math]O(log(n))[/math] операций слияния, а значит и каждый элемент будет задействован в сравниниях не более [math]O(log(n))[/math] раз. Элементов [math]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