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