Изменения

=[[Файл:Example.png|900px]]  ==Модификация процедуры слияния подмассивов (Galloping Mode)===

Не сложно заметить, что чем меньше массивов, тем меньше произойдёт операций слияния, но чем их длины больше, тем дольше эти слияния будут происходить. На малом количестве длинных массивов хорошо помогает вышеописанный метод '''Galloping Mode'''. Хоть он и не даёт асимптотического выигрыша, но уменьшает константу.Пусть <tex>k</tex> {{---}} число кусков, на которые разбился наш исходный массив, очевидно <tex> k </tex> = <tex dpi=150> \ulcorner \frac{n}{minrun} \urcorner </tex>. Главный факт, который нам понадобится для доказательства нужной оценки времени работы в <tex>О(nlog(n))</tex> {{---}} это то, что сливаемые массивы '''всегда''' имеют примерно одинаковую длинну. То есть Можно сказать больше {{---}} пока <tex>k > 3</tex> сливаемые подмассивы будут именно одинаковой длинны (данный факт хорошо виден на примере). Безусловно, после разбения массива на блоки длинной <tex>run_1minrun</tex>последний блок может быть отличен от данного значения практически в 2 раза, но эти 20-30 элементов разницы при <tex>run_2n</tex> такиепорядка <tex>10^6</tex> практически не повлияют на время работы. Мы выяснили, что при слиянии, длинна образовавшегося слитого массива увеличивается <tex>run_1.size \gg run_2approx</tex> 2 раза.sizeТаким образом получаем, что каждый подмассив <tex>run_i</tex> будут слиты только тогда, когда размеры соответствующих подмассивовможет участвовать в не более <tex>O(log(n))</tex> операций слияния, а значит и каждый элемент будет задействован в которые они войдут будут примерно равнысравниниях не более <tex>O(log(n))</tex> раз. Например, если на вход подан массив Элементов <tex>64, 32, 16, 8, 4, 2, 1n</tex>, то, временно забыв про понятие откуда получаем оценку в <tex>minrunO(nlog(n))</tex>, '''Timsort''' сделает следующие слияния:# 64, 32, 16, 8, 4, 2, 1, 1# 64, 32, 16, 8, 4, 2, 2# 64, 32, 16, 8, 4, 4# 64, 32, 16, 8, 8# 64, 32, 16, 16# 64, 32, 32# 64, 64# 128.

При сливании двух Также нужно сказать про [[Сортировка вставками | сортировку вставками]], которая используется для сортировки подмассивов <tex>run_1run_i</tex>: в нашем случае,алгоритм работает за <tex>run_2O(minrun + inv)</tex> будет произведенно , где <tex>inv</tex>O(run_1{{---}} число обменов элементов входного массива, равное числу инверсий.size + run_2.size)C учетом значения <tex>k</tex> операций сравнения. Результирующий подмассив , получим, что сортировка всех блоков может занять <tex>run_{12}O(minrun + inv) * k = O(minrun + inv) * </tex> будет удовлетворять выражению <texdpi=150>run_\ulcorner \frac{n}{12minrun}.size \approx 2run_1.size \approx 2run_2.size urcorner </tex>. Таким образом, каждый подмассив Что в худшем случае (<tex>run_iinv</tex> может поучаствовать в не более = <texdpi=150 >O(log\frac{minrun*(n)minrun - 1)}{2} </tex> операций слияния, а значит и каждый элемент будет задействован в сравниниях не более ) может занимать <tex>O(log(n)+ n*minrun)</tex> развремени. Элементов Откуда видно, что константа <tex>nminrun</tex>, откуда и получаем соответствующую оценку в играет не малое значение: при большом <tex>O(nlog(n))minrun</tex>слияний будет меньше, а сортировки вставками будут выполняться долго. Причём эти функцию растут с разной скоростью, поэтому видимо и был выбран вот такой оптимальный диапазон {{---}} от 32 до 64.