143
правки
Изменения
Нет описания правки
* <tex>\mathtt {n}</tex> {{---}} размер входного массива.
* <tex>\mathtt {run}</tex> {{---}} подмассив во входном массиве, который обязан быть упорядоченным одним из двух способов:
** строго по убыванию <tex>\mathtt {a_{i} > a_{i + 1} > ...\dots} </tex>. ** нестрого по возрастанию <tex>\mathtt {a_{i} \leqslant a_{i + 1} \leqslant ...\dots} </tex>.
* <tex>\mathtt {minrun} </tex> {{---}} минимальный размер подмассива, описанного в предыдущем пункте.
Рассмотрим процедуру слияния двух массивов:
<tex>A = {1, 2, 3, ...\dots, 9999, 10000}</tex>
<tex>B = {20000, 20001, 20002, ...\dots, 29999, 30000}</tex>
Вышеуказанная процедура для них сработает, но каждый раз на её четвёртом пункте нужно будет выполнить одно сравнение и одно копирование. В итоге <tex>10000</tex> сравнений и <tex>10000</tex> копирований. '''Timsort''' предлагает в этом месте модификацию, которая получила называет '''галоп'''. Алгоритм следующий:
* Конец.
Для вышеописанных массивов <tex>\mathtt{A, B}</tex> алгоритм выглядит следующим образом:
Первые <tex>7</tex> итераций сравниваются числа <tex>1, 2, 3, 4, 5, 6, 7</tex> из массива <tex>\mathtt{A}</tex> с числом <tex>20000</tex>, так как <tex>20000</tex> больше, то элементы массива <tex>\mathtt{A}</tex> копируются в результирующий. Начиная со следующей итерации алгоритм переходит в режим '''галопа''': сравнивает с числом <tex>20000</tex> последовательно элементы <tex>8, 10, 14, 22, 38, 7+2^{i - 1}, ...\dots, 10000 </tex> массива <tex>\mathtt{A}</tex> <tex>( \thicksim\log{n}</tex> сравнений<tex>)</tex>. После того как конец массива <tex>\mathtt{A}</tex> достигнут и известно, что он весь меньше <tex>\mathtt{B}</tex>, нужные данные из массива <tex>\mathtt{A}</tex> копируются в результирующий.
== Доказательство времени работы алгоритма ==
