Изменения
→Шаг 1. Вычисление minrun
** Оно не должно быть слишком маленьким, так как чем меньше подмассив, тем больше итераций слияния подмассивов придётся выполнить на последнем шаге алгоритма. Оптимальная величина для <tex dpi = 150> \frac{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{\frac{{n}}{minrun}} </tex> будет степенью двойки.
* Конец.
minRunLength(n)
