1632
правки
Изменения
м
rollbackEdits.php mass rollback
'''Timsort''' {{---}} гибридный алгоритм сортировки, сочетающий различные подходы.
Данный алгоритм является относительно новым и был придуман Тимом Петерсом. На массивах данных, которые содержат упорядоченный подмасивыупорядоченные подмассивы, алгоритм Тима Петерса показывает себя намного лучше других сортировок. В настоящее время '''Timsort''' является стандартной сортировкой в '''Python''' и '''GNU Octave''', реализован в '''OpenJDK 7''' и '''Android JDK 1.5'''.
== Основная идея алгоритма ==
* '''Шаг 1'''. Берем старшие 6 бит числа <tex>n</tex> и добавляем единицу, если в оставшихся младших битах есть хотя бы один ненулевой.
Нетрудно понять, что после таких вычислений, <tex>\mathtt{\dfrac{{n}}{minrun}} </tex> будет степенью равно степени двойки или немного меньше степени двойки.
* Конец.
'''int''' minRunLength(n):
