Изменения

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

Алгоритм '''Timsort''' состоит из нескольких шаговчастей:* Начало.* '''Шаг №11''': по . По специальному алгоритму входной массив разделяется на подмассивы.* '''Шаг 2'''. Каждый подмассив сортируется [[Сортировка вставками | сортировкой вставками]], [[Сортировка выбором | сортировкой выбором]] или любой другой устойчивой сортировкой.* '''Шаг 3'''. Отсортированные подмассивы собираются в единый массив с помощью модифицированной [[Сортировка слиянием | сортировки слиянием]].* Конец.

* '''Шаг №2''': Рассмотрим теперь каждый подмассив сортируется [[Сортировка вставками | сортировкой вставками]] или [[Сортировка выбором | сортировкой выбором]]. * '''Шаг №3''': отсортированные подмассивы собираются шаг в единый массив с помощью модифицированной [[Сортировка слиянием | сортировки слиянием]]отдельности.

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

* '''Шаг 0'''. Число <tex>minrun</tex> определяется на основе <tex> n </tex>, исходя из следующих принципов:

** Оно не должно быть слишком маленьким, так как чем меньше подмассив {{---}} , тем больше итераций слияния подмассивов придётся выполнить на последнем шаге алгоритма. Оптимальная величина для <texdpi = 150> \frac{n / }{minrun } </tex> {{---}} ''степень двойки''. Это требование обусловлено тем, что алгоритм слияния подмассивов наиболее эффективно работает на подмассивах примерно равного размера.** Согласно авторским экспериментам: *** При <tex> minrun > 256 </tex> нарушается пункт <tex>1</tex>.*** При <tex> minrun < 8 </tex> нарушается пункт Автором алгоритма было выбрано оптимальное значение, которое принадлежит диапазону <tex>2</tex>.*** Наиболее эффективные значения <tex> minrun </tex> из диапозона <tex> ([32; 65) </tex>(подробнее о том, почему так, будет сказано ниже).*** Исключение — : если <tex> n < 64 </tex>, тогда <tex> n = minrun </tex> и '''Timsort''' превращается в сортировку вставками.* '''Шаг 1'''. Берем старшие 6 бит числа <tex> n </tex> и добавляем единицу, если в оставшихся младших битах есть хотя бы один ненулевой.  Нетрудно понять, что после таких вычислений, <tex dpi = 150> \frac{n}{minrun} </tex> будет степенью двойки.

int GetMinrun(int n) { int flag = 0; /* станет 1 если среди сдвинутых битов есть хотя бы 1 ненулевой */ while (n >= 64) { flag |= n & 1; n >>= 1; } return n + flag; } ===Шаг №22. Алгоритм разбиения на подмассивы и их сортировка===

* '''Шаг 1'''. Начиная с текущего элемента, идет поиск во входном массиве упорядоченного подмассива <tex>run</tex>. По определению, в <tex>run</tex> однозначно войдет текущий элемент и следующий за ним. Если получившийся подмассив упорядочен по убыванию {{---}} , то после вычисления <tex>run</tex> для текущего массива элементы переставляются так, чтобы они шли по возрастанию.

===Шаг №33. Слияние===Нужно объединить полученные подмассивы для получения результирующего упорядоченного массива. Для достижения эффективности, объединение должно ''объединять подмассивы примерно равного размера'' и ''cохранять стабильность алгоритма (не делать бессмысленных перестановок)''.

* '''Шаг 0'''. Создается пустой стек пар <tex> < </tex>индекс начала подмассива<tex> > </tex> {{---}} <tex> < </tex>, размер подмассива<tex> > </tex>.

* '''Шаг 2'''. Добавляется в стек пара данных <tex> < </tex>индекс начала текущего подмассива<tex> > </tex> {{---}} <tex> < </tex>, его размер<tex> > </tex>.

* '''Шаг 4'''.Повторяем пока выражение (<tex>Z > X + Y</tex> && <tex>~and~ Y > X</tex>) не станет истинным ** Если размер стека не меньше <tex>3 </tex> и <tex>Z \leqslant X + Y</tex> {{---}} сливаем <tex>Y</tex> c <tex>min(X,Z)</tex>.

** Возвращаемся '''Шаг 5'''. Если всего осталось <tex> 3 </tex> подмассива, которые сейчас в п.6стеке, то сливаем их в правильном порядке, иначе же переходим к шагу 2.

Возьмем <tex>n = 356</tex>. При таком <tex>n</tex> <tex>minrun</tex> оказался равным <tex>45</tex>. Ниже представлена работа алгоритма.

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

 * '''Шаг 1'''.На каждой операции копирования элемента из временного или большего подмассива в результирующий запоминается, из какого именно подмассива был элемент. * '''Шаг 2'''. Если уже некоторое количество элементов (например, в данной реализации алгоритма '''JDK 7''' это число равно 7) было взято из одного и того же массива {{---}} предполагается, что и дальше придётся брать данные из него. Чтобы подтвердить эту идею, алгоритм переходит в режим '''«галопа»галопа''', то есть перемещается по массиву-претенденту на поставку следующей большой порции данных бинарным поиском (массив упорядочен) текущего элемента из второго соединяемого массива. * '''Шаг 43'''. В момент, когда данные из текущего массива-поставщика больше не подходят (или был достигнут конец массива), данные копируются целиком.

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

Пусть <tex>k</tex> {{---}} число кусков, на которые разбился наш исходный массив, очевидно <tex> k </tex> = <tex dpi=150> \ulcorner left\lceil \frac{n}{minrun} \urcorner right\rceil </tex>.  Главный факт, который нам понадобится для доказательства нужной оценки времени работы в <tex>О(nlogO(n)\log{n})</tex> {{---}} это то, что сливаемые массивы '''всегда''' имеют примерно одинаковую длинну. Можно сказать больше {{---}} : пока <tex>k > 3</tex> сливаемые подмассивы будут именно одинаковой длинны (данный факт хорошо виден на примере). Безусловно, после разбения разбиения массива на блоки длинной длиной <tex>minrun</tex> последний блок может быть отличен от данного значения практически в 2 раза, но эти 20-30 число элементов разницы при в нём не превосходит константы <tex>nminrun </tex> порядка <tex>10^6</tex> практически не повлияют на время работы.

Мы выяснили, что при слиянии, длинна образовавшегося слитого массива увеличивается в <tex>\approx2</tex> 2 раза. Таким образом получаем, что каждый подмассив <tex>run_i</tex> может участвовать в не более <tex>O(\log({n)})</tex> операций слияния, а значит и каждый элемент будет задействован в сравниниях не более <tex>O(\log({n)})</tex> раз. Элементов <tex>n</tex>, откуда получаем оценку в <tex>O(nlog(n)\log{n})</tex>.

Также нужно сказать про [[Сортировка вставками | сортировку вставками]], которая используется для сортировки подмассивов <tex>run_i</tex>: в нашем случае, алгоритм работает за <tex>O(minrun + inv)</tex>, где <tex>inv</tex> {{---}} число обменов элементов входного массива, равное числу инверсий. C учетом значения <tex>k</tex>, получим, что сортировка всех блоков может занять <tex>O(minrun + inv) * \cdot k = O(minrun + inv) * \cdot </tex><tex dpi=150>\ulcorner left\lceil \frac{n}{minrun} \urcorner right\rceil </tex>. Что в худшем случае (<tex>inv</tex> = <tex dpi=150 > (inv = \frac{minrun*(minrun - 1)}{2} )</tex>) может занимать <tex>O(n + n*\cdot minrun) </tex> времени. Откуда видно, что константа <tex>minrun</tex> играет не малое немалое значение: при большом <tex>minrun</tex> слияний будет меньше, а сортировки вставками будут выполняться долго. Причём эти функцию функции растут с разной скоростью, поэтому видимо и ещё после эксперементов на различных значениях и был выбран вот такой оптимальный диапазон {{---}} от <tex>32 </tex> до <tex>64</tex>.