Изменения

* Начало.* '''Шаг 0'''. Число <tex>minrun</tex> определяется на основе <tex> n </tex>, исходя из принципов:** Не должно быть слишком большим, поскольку к подмассиву размера <tex> minrun </tex> будет в дальнейшем применена сортировка вставками (эффективна только на небольших массивах).** Оно не должно быть слишком маленьким, так как чем меньше подмассив {{---}} тем больше итераций слияния подмассивов придётся выполнить на последнем шаге алгоритма. Оптимальная величина для <tex> 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> и добавляем единицу, если в оставшихся младших битах есть хотя бы один ненулевой.* Конец.

* '''Шаг 0'''. Указатель текущего элемента ставится в начало входного массива.* '''Шаг 1'''. Начиная с текущего элемента, идет поиск во входном массиве упорядоченного подмассива <tex>run</tex>. По определению, в <tex>run</tex> однозначно войдет текущий элемент и следующий за ним. Если получившийся подмассив упорядочен по убыванию {{---}} элементы переставляются так, чтобы они шли по возрастанию.* '''Шаг 2'''. Если размер текущего <tex>run</tex> меньше <tex>minrun</tex>, тогда выбираются следующие за найденным подмассивом <tex>run</tex> элементы в количестве <tex> minrun - size(run) </tex>. Таким образом, на выходе будет получен подмассив размером большим или равный <tex>minrun</tex>, часть которого (в лучшем случае {{---}} он весь) упорядочена.* '''Шаг 3'''. К данному подмассиву применяем сортировка вставками. Так как размер подмассива невелик и часть его уже упорядочена {{---}} сортировка работает эффективно. * '''Шаг 4'''. Указатель текущего элемента ставится на следующий за подмассивом элемент. * '''Шаг 5'''. Если конец входного массива не достигнут {{---}} переход к пункту 2шагу 1.

* '''Шаг 0'''. Создается пустой стек пар <tex> < </tex>индекс начала подмассива<tex> > </tex> {{---}} <tex> < </tex>размер подмассива<tex> > </tex>.* '''Шаг 1'''. Берется первый упорядоченный подмассив.* '''Шаг 2'''. Добавляется в стек пара данных <tex> < </tex>индекс начала текущего подмассива<tex> > </tex> {{---}} <tex> < </tex>его размер<tex> > </tex>.* '''Шаг 3'''. Пусть <tex>X,Y,Z </tex> {{---}} длины верхних трех интервалов, которые лежат в стеке. Причем <tex>X</tex> {{---}} это последний элемент стека. * '''Шаг 4'''.Повторяем пока выражение (<tex>Z > X + Y</tex> && <tex>Y > X</tex>) не станет истинным

* Начало. * '''Шаг 0'''. Создается временный массив в размере меньшего из сливаемых подмассивов.

* '''Шаг 1'''. Меньший из подмассивов копируется во временный массив, но надо учесть, что если меньший подмассив <tex>-</tex> правый, то ответ (результат сливания) формируется справа налево. Дабы избежать данной путаницы, лучше копировать всегда левый подмассив во временный. На скорости это практически не отразится.

* '''Шаг 2'''. Ставятся указатели текущей позиции на первые элементы большего и временного массива.

* '''Шаг 3'''. На каждом шаге рассматривается значение текущих элементов в большем и временном массивах, берется меньший из них, копируется в новый отсортированный массив. Указатель текущего элемента перемещается в массиве, из которого был взят элемент.

* '''Шаг 4'''. Предыдущий пункт повторяется, пока один из массивов не закончится.

* '''Шаг 5'''.Все элементы оставшегося массива добавляются в конец нового массива. * Конец.

* Начинается процедура слиянияНачало.

* На каждой операции копирования элемента из временного или большего подмассива в результирующий запоминается, из какого именно подмассива был элемент'''Шаг 0'''. Начинается процедура слияния.

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

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