== Основная идея алгоритма ==
<tex>*</tex> По специальному алгоритму входной массив разделяется на подмассивы.
<tex>*</tex> Каждый подмассив сортируется [[Сортировка вставками | сортировкой вставками]] или [[Сортировка выбором | сортировкой выбором]].
<tex>*</tex> Отсортированные подмассивы собираются в единый массив с помощью модифицированной [[Сортировка слиянием | сортировки слиянием]].
===Используемые понятия и комментарии===
<tex>*</tex> <tex>n</tex> — размер входного массива.
<tex>*</tex> <tex>run</tex> — некоторый подмассив во входном массиве, который обязан быть упорядоченным одним из двух способов:
# строго по убыванию <tex> a_{i} > a_{i + 1} > ... </tex>.
# нестрого по возрастанию <tex> a_{i} \le a_{i + 1} \le ... </tex>.
<tex>*</tex> <tex>minrun</tex> — минимальный размер подмассива, описанного в предыдущем пункте.
Алгоритм '''Timsort''' состоит из нескольких шагов:
Число <tex>minrun</tex> определяется на основе <tex> n </tex>, исходя из принципов:
<tex> * </tex> Оно не должно быть слишком большим, поскольку к подмассиву размера <tex> minrun </tex> будет в дальнейшем применена сортировка вставками, а она эффективна только на небольших массивах.
<tex> * </tex> Оно не должно быть слишком маленьким, так как чем меньше подмассив — тем больше итераций слияния подмассивов придётся выполнить на последнем шаге алгоритма. Оптимальная величина для <tex> n / minrun </tex> — ''степень двойки''. Это требование обусловлено тем, что алгоритм слияния подмассивов наиболее эффективно работает на подмассивах примерно равного размера.
<tex>*</tex> Согласно авторским экспериментам:
# При <tex> minrun > 256 </tex> нарушается пункт <tex>1</tex>.
# При <tex> minrun < 8 </tex> нарушается пункт <tex>2</tex>.
Если данные изначального массива достаточно близки к случайным, то размер упорядоченных подмассивов близок к <tex>minrun</tex>. Если в изначальных данных были упорядоченные диапазоны, то упорядоченные подмассивы могут иметь размер, превышающий <tex>minrun</tex>.
<tex>*</tex> Итак, нужно объединить полученные подмассивы для получения результирующего упорядоченного массива. Для достижения эффективности, объединение должно удовлетворять требованиям:
# Объединять подмассивы примерно равного размера
# Сохранить стабильность алгоритма (не делать бессмысленных перестановок). [[Файл:Merge2mas.png|400px|right]]
===Описание процедуры слияния===
<tex>*</tex> Создается временный массив в размере меньшего из сливаемых подмассивов.
<tex>*</tex> Меньший из подмассивов копируется во временный массив, но надо учесть, что если меньший подмассив <tex>-</tex> правый, то ответ (результат сливания) формируется справа налево. Дабы избежать данной путаницы, лучше копировать всегда левый подмассив во временный. На скорости это практически не отразится.
<tex>*</tex> Ставятся указатели текущей позиции на первые элементы большего и временного массива.
<tex>*</tex> На каждом шаге рассматривается значение текущих элементов в большем и временном массивах, берется меньший из них, копируется в новый
отсортированный массив. Указатель текущего элемента перемещается в массиве, из которого был взят элемент.
<tex>*</tex> Предыдущий пункт повторяется, пока один из массивов не закончится.
<tex>*</tex> Все элементы оставшегося массива добавляются в конец нового массива.
===Модификация процедуры слияния подмассивов (Galloping Mode)===
Вышеуказанная процедура для них сработает, но каждый раз на её четвёртом пункте нужно будет выполнить одно сравнение и одно копирование. В итоге 10000 сравнений и 10000 копирований. Алгоритм '''Timsort''' предлагает в этом месте модификацию, которая получила называет '''«галоп»'''. Алгоритм следующий:
<tex>*</tex> Начинается процедура слияния.
<tex>*</tex> На каждой операции копирования элемента из временного или большего подмассива в результирующий запоминается, из какого именно подмассива был элемент.
<tex>*</tex> Если уже некоторое количество элементов (в данной реализации алгоритма это число равно 7) было взято из одного и того же массива — предполагается, что и дальше придётся брать данные из него. Чтобы подтвердить эту идею, алгоритм переходит в режим '''«галопа»''', то есть перемещается по массиву-претенденту на поставку следующей большой порции данных бинарным поиском (массив упорядочен) текущего элемента из второго соединяемого массива.
<tex>*</tex> В момент, когда данные из текущего массива-поставщика больше не подходят (или был достигнут конец массива), данные копируются целиком.
Для вышеописанных массивов <tex> A, B </tex> алгоритм выглядит следующим образом:
== Источники ==
<tex>*</tex> 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.
<tex>*</tex> Magnus Lie Hetland Python Algorithms: Mastering Basic Algorithms in the Python Language. — Apress, 2010. — 336 с.
<tex>*</tex> [http://ru.wikipedia.org/wiki/Timsort Wikipedia - Timsort]
<tex>*</tex> [http://habrahabr.ru/company/infopulse/blog/133303/ Habrahabr - Алгоритм сортировки Timsort]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Сортировки]]
