Изменения

Для Главный факт, который нам понадобится для доказательства нужной оценки времени работы алгоритма в <tex>О(nlog(n))</tex> - это то, что сливаемые массивы '''Timsortвсегда''' составим рекуррентное соотношениеимеют примерно одинаковую длинну. Пусть То есть подмассивы <tex>run_1</tex>, <tex> T(n) run_2</tex> — время сортировки массива длины nтакие, что <tex>run_1.size \gg run_2. Рассмотрим последнее слияние двух size</tex> будут слиты только тогда, когда размеры соответствующих подмассивов , в которые они войдут будут примерно равны. Например, если на вход подан массив <tex> run1 64, 32, 16, 8, 4, 2, 1</tex> и , то, временно забыв про понятие <tex> run2 minrun</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> T(n) = T(run1.size) + T(run2.size) + O(run1.size + run2.size) run_1</tex>. Алгоритм построен таким образом, что сливаемые подмассивы имеют примерно равные размеры. Таким образом можно считать:  <tex> T(n) = T(run1.size) + T(run2.size) + run_2</tex> будет произведенно <tex>O(run1run_1.size + run2run_2.size) </tex> операций сравнения. Результирующий подмассив <tex> \approx 2T(n/2) + O(n) \approx run_{12}</tex> будет удовлетворять выражению <tex> 4T(n/4) + 2O(n) run_{12}.size \approx \dots 2run_1.size \approx 2^{k}T(1) + kO(n) </tex>2run_2. Осталось оценить <tex>ksize </tex>. <tex>n/minrun</tex> - количество сливаемых блоковТаким образом, откуда следует, что каждый подмассив <tex>2^{k} = n/minrunrun_i</tex>, значит может поучаствовать в не более <tex> k = O(log(n/minrun))</tex>.  операций слияния, а значит и каждый элемент будет задействован в сравниниях не более <tex>TO(n) \approx 2^{k}T(1) + kOlog(n) </tex> = <tex> log(n/minrun) + </tex>раз. Элементов <tex>log(n/minrun)O(n)</tex> , откуда и получаем соответствующую оценку в <tex> = O(nlog(n)). </tex>