* '''Шаг 0'''. Создается временный массив в размере меньшего из сливаемых подмассивов.
* '''Шаг 1'''. Меньший из подмассивов копируется во временный массив, но надо учесть, что если меньший подмассив <tex>{{-</tex> --}} правый, то ответ (результат сливания) формируется справа налево. Дабы избежать данной путаницы, лучше копировать всегда левый подмассив во временный. На скорости это практически не отразится.
* '''Шаг 2'''. Ставятся указатели текущей позиции на первые элементы большего и временного массива.
Также нужно сказать про [[Сортировка вставками | сортировку вставками]], которая используется для сортировки подмассивов <tex>run_i</tex>: в нашем случае, алгоритм работает за <tex>O(minrun + inv)</tex>, где <tex>\mathtt{inv}</tex> {{---}} число обменов элементов входного массива, равное числу инверсий. C учетом значения <tex>\mathtt{k}</tex> получим, что сортировка всех блоков может занять <tex>O(minrun + inv) \cdot k = O(minrun + inv) \cdot </tex><tex dpi=150>\left\lceil \frac{n}{minrun} \right\rceil </tex>. Что в худшем случае <tex dpi=150 >(inv = \frac{minrun(minrun - 1)}{2} )</tex> может занимать <tex>O(n \cdot minrun) </tex> времени. Откуда видно, что константа <tex>\mathtt{minrun}</tex> играет немалое значение: при большом <tex>\mathtt{minrun}</tex> слияний будет меньше, а сортировки вставками будут выполняться долго. Причём эти функции растут с разной скоростью, поэтому и ещё после эксперементов на различных значениях и был выбран оптимальный диапазон {{---}} от <tex>32</tex> до <tex>64</tex>.
== Некорректность timsort в Java ==
Метод <tex>\mathtt{mergeCollapse}</tex> (Java) - который сливает серии(<tex>\mathtt{runLen}</tex>):
'''private void''' mergeCollapse() { //метод, содержащий ошибку
'''while''' (stackSize > 1) {
'''int''' n = stackSize - 2;
'''if''' (n > 0 && runLen[n-1] <= runLen[n] + runLen[n+1]) {
'''if''' (runLen[n - 1] < runLen[n + 1])
n--;
mergeAt(n);
} '''else if''' (runLen[n] <= runLen[n + 1]) {
mergeAt(n);
} '''else''' {
'''break'''; // инвариант установлен
}
}
}
В результате выполнения метода <tex>\mathtt{mergeCollapse}</tex>, утверждается что для последних трех серий выполняются следующие условия(инвариант):
*<tex> runLen[n - 2] > runLen[n - 1] + runLen[n] </tex>
*<tex>runLen[n - 1] > runLen[n] </tex>
Утверждается, что этого достаточно, но самом деле нет. Рассмотрим пример.
Пусть <tex>\mathtt{runLen}</tex> содержит следующий набор длин:
<tex> 23, 16, 5, 4, 6 </tex>
На первом шаге в цикле будут объединены серии : <tex>5</tex> и <tex>4</tex> (<tex>5 < 4 + 6</tex>, <tex>5 < 6</tex>). Получим:
<tex> 23, 16, 9, 6 </tex>
На втором шаге,в последней тройке устанавливается инвариант и <tex>\mathtt{mergeCollapse}</tex> завершает свою работу, но инвариант для всего массива не восстановлен: он нарушается в первой тройке, так как <tex>23 < 16 + 9</tex>.
В результате нарушения инварианта, длины серий растут медленнее, чем ожидалось, в результате чего их кол-во превышает <tex>\mathtt{runLen.Length}</tex>, что приводит к <tex>\mathtt{ArrayOutOfBoundsException}</tex>.
Основная идея исправления ошибки {{---}} проверять, что инвариант соблюдается для четырёх последних серий в runLen вместо трёх.
Таким образом, получаем следующее исправление:
'''private void''' newMergeCollapse() { //исправление
'''while''' (stackSize > 1) {
int n = stackSize - 2;
'''if''' ( (n >= 1 && runLen[n-1] <= runLen[n] + runLen[n+1])
|| (n >= 2 && runLen[n-2] <= runLen[n] + runLen[n-1])) {
'''if''' (runLen[n - 1] < runLen[n + 1])
n--;
} '''else if''' (runLen[n] > runLen[n + 1]) {
break; // Инвариант установлен
}
mergeAt(n);
}
}
==См. также==
* [http://habrahabr.ru/company/infopulse/blog/133303/ Habrahabr - Алгоритм сортировки Timsort]
* [http://habrahabr.ru/post/251751/ Habrahabr - Доказательство некорректности алгоритма сортировки Android, Java и Python]
