Изменения
Нет описания правки
* '''Шаг 0'''. Число <tex>\mathtt{minrun}</tex> определяется на основе <tex>\mathtt{n}</tex>, исходя из следующих принципов:
** Не должно быть слишком большим, поскольку к подмассиву размера <tex>\mathtt{minrun}</tex> будет в дальнейшем применена сортировка вставками (эффективна только на небольших массивах).
** Оно не должно быть слишком маленьким, так как чем меньше подмассив, тем больше итераций слияния подмассивов придётся выполнить на последнем шаге алгоритма. Оптимальная величина для <tex dpi = 150> \mathtt{\fracdfrac{n}{minrun}} </tex> {{---}} ''степень двойки''. Это требование обусловлено тем, что алгоритм слияния подмассивов наиболее эффективно работает на подмассивах примерно равного размера.
** Автором алгоритма было выбрано оптимальное значение, которое принадлежит диапазону <tex> [32; 65) </tex> (подробнее о том, почему так, будет сказано ниже).
** Исключение: если <tex> \mathtt{n < 64} </tex>, тогда <tex> \mathtt{n = minrun} </tex> и '''Timsort''' превращается в сортировку вставками.
* '''Шаг 1'''. Берем старшие 6 бит числа <tex>\mathtt{n} </tex> и добавляем единицу, если в оставшихся младших битах есть хотя бы один ненулевой.
Нетрудно понять, что после таких вычислений, <tex dpi=150>\mathtt{\fracdfrac{{n}}{minrun}} </tex> будет степенью двойки.
* Конец.
'''int''' minRunLength(n)
== Доказательство времени работы алгоритма ==
Не сложно заметить, что чем меньше массивов, тем меньше произойдёт операций слияния, но чем их длины больше, тем дольше эти слияния будут происходить. На малом количестве длинных массивов хорошо помогает вышеописанный метод '''Galloping Mode'''. Хоть он и не даёт асимптотического выигрыша, но уменьшает константу.
Пусть <tex>\mathtt{k}</tex> {{---}} число кусков, на которые разбился наш исходный массив, очевидно <tex>\mathtt{k} </tex> = <tex dpi=150> \left\lceil \mathtt{\fracdfrac{n}{minrun}} \right\rceil </tex>.
Главный факт, который нам понадобится для доказательства нужной оценки времени работы в <tex>O(n \log{n})</tex> {{---}} это то, что сливаемые массивы '''всегда''' имеют примерно одинаковую длину. Можно сказать больше: пока <tex>k > 3</tex> сливаемые подмассивы будут именно одинаковой длины (данный факт хорошо виден на примере). Безусловно, после разбиения массива на блоки длиной <tex>\mathtt{minrun}</tex> последний блок может быть отличен от данного значения, но число элементов в нём не превосходит константы <tex>\mathtt{minrun}</tex>.
Мы выяснили, что при слиянии, длинна образовавшегося слитого массива увеличивается в <tex>\approx 2</tex> раза. Таким образом получаем, что каждый подмассив <tex>\mathtt{run_i}</tex> может участвовать в не более <tex>O(\log{n})</tex> операций слияния, а значит и каждый элемент будет задействован в сравниниях не более <tex>O(\log{n})</tex> раз. Элементов <tex>\mathtt{n}</tex>, откуда получаем оценку в <tex>O(n\log{n})</tex>.
Также нужно сказать про [[Сортировка вставками | сортировку вставками]], которая используется для сортировки подмассивов <tex>run_i</tex>: в нашем случае, алгоритм работает за <tex>O(\mathtt{minrun + inv})</tex>, где <tex>\mathtt{inv}</tex> {{---}} число обменов элементов входного массива, равное числу инверсий. C учетом значения <tex>\mathtt{k}</tex> получим, что сортировка всех блоков может занять <tex>O(\mathtt{minrun + inv}) \cdot k = O(\mathtt{minrun + inv}) \cdot </tex><tex dpi=150>\left\lceil \mathtt{\fracdfrac{n}{minrun}} \right\rceil </tex>. Что в худшем случае <tex dpi=120>(\mathtt{inv = \fracdfrac{minrun(minrun - 1)}{2}} )</tex> может занимать <tex>O(\mathtt{n \cdot minrun}) </tex> времени. Откуда видно, что константа <tex>\mathtt{minrun}</tex> играет немалое значение: при большом <tex>\mathtt{minrun}</tex> слияний будет меньше, а сортировки вставками будут выполняться долго. Причём эти функции растут с разной скоростью, поэтому и ещё после эксперементов на различных значениях и был выбран оптимальный диапазон {{---}} от <tex>32</tex> до <tex>64</tex>.
==См. также==
