Изменения

** строго по убыванию <tex> \mathtt {a_{i} > a_{i + 1} > ... } </tex>. ** нестрого по возрастанию <tex> \mathtt {a_{i} \le a_{i + 1} \le ... } </tex>.

* '''Шаг 0'''. Число <tex>\mathtt{minrun}</tex> определяется на основе <tex> \mathtt{n }</tex>, исходя из следующих принципов:** Не должно быть слишком большим, поскольку к подмассиву размера <tex> \mathtt{minrun }</tex> будет в дальнейшем применена сортировка вставками (эффективна только на небольших массивах).

* '''Шаг 1'''. Берем старшие 6 бит числа <tex> \mathtt {n } </tex> и добавляем единицу, если в оставшихся младших битах есть хотя бы один ненулевой.

На данном этапе у нас есть входной массив, его размер <tex>\mathtt{n}</tex> и вычисленное число <tex>\mathtt{minrun}</tex>. Обратим внимание, что если данные изначального массива достаточно близки к случайным, то размер упорядоченных подмассивов близок к <tex>\mathtt{minrun}</tex>,. Но если в изначальных данных были упорядоченные диапазоны, то упорядоченные подмассивы могут иметь размер, превышающий <tex>\mathtt{minrun}</tex>. [[Файл:MinrunExample.png‎ |300px|thumb|right]]

* '''Шаг 1'''. Начиная с текущего элемента, идет поиск во входном массиве упорядоченного подмассива <tex>\mathtt{run}</tex>. По определению, в <tex>\mathtt{run}</tex> однозначно войдет текущий элемент и следующий за ним. Если получившийся подмассив упорядочен по убыванию, то после вычисления <tex>\mathtt{run}</tex> для текущего массива элементы переставляются так, чтобы они шли по возрастанию.* '''Шаг 2'''. Если размер текущего <tex>\mathtt{run}</tex> меньше <tex>\mathtt{minrun}</tex>, тогда выбираются следующие за найденным подмассивом <tex>\mathtt{run}</tex> элементы в количестве <tex> minrun - size(run) </tex>. Таким образом, на выходе будет получен подмассив размером большим или равный <tex>\mathtt{minrun}</tex>, часть которого (в лучшем случае {{---}} он весь) упорядочена.

Возьмем <tex>n = 356</tex>. При таком <tex>\mathtt{n}</tex> <tex>\mathtt{minrun}</tex> оказался равным <tex>45</tex>. Ниже представлена работа алгоритма.

Для вышеописанных массивов <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}, ..., 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> копируются в результирующий.

Пусть <tex>\mathtt{k}</tex> {{---}} число кусков, на которые разбился наш исходный массив, очевидно <tex> \mathtt{k } </tex> = <tex dpi=150> \left\lceil \frac{n}{minrun} \right\rceil </tex>.

Главный факт, который нам понадобится для доказательства нужной оценки времени работы в <tex>O(n \log{n})</tex> {{---}} это то, что сливаемые массивы '''всегда''' имеют примерно одинаковую длину. Можно сказать больше: пока <tex>k > 3</tex> сливаемые подмассивы будут именно одинаковой длины (данный факт хорошо виден на примере). Безусловно, после разбиения массива на блоки длиной <tex>\mathtt{minrun}</tex> последний блок может быть отличен от данного значения, но число элементов в нём не превосходит константы <tex> \mathtt{minrun }</tex>.

Мы выяснили, что при слиянии, длинна образовавшегося слитого массива увеличивается в <tex>\approx 2</tex> раза. Таким образом получаем, что каждый подмассив <tex>\mathtt{run_i}</tex> может участвовать в не более <tex>O(\log{n})</tex> операций слияния, а значит и каждый элемент будет задействован в сравниниях не более <tex>O(\log{n})</tex> раз. Элементов <tex>\mathtt{n}</tex>, откуда получаем оценку в <tex>O(n\log{n})</tex>.

Также нужно сказать про [[Сортировка вставками | сортировку вставками]], которая используется для сортировки подмассивов <tex>run_i</tex>: в нашем случае, алгоритм работает за <tex>O(minrun + inv)</tex>, где <tex>\mathtt{inv}</tex> {{---}} число обменов элементов входного массива, равное числу инверсий. C учетом значения <tex>\mathtt{k}</tex> получим, что сортировка всех блоков может занять <tex>O(minrun + inv) \cdot k = O(minrun + inv) \cdot </tex><tex dpi=150>\left\lceil \frac{n}{minrun} \right\rceil </tex>. Что в худшем случае <tex dpi=150 >(inv = \frac{minrun(minrun - 1)}{2} )</tex> может занимать <tex>O(n \cdot minrun) </tex> времени. Откуда видно, что константа <tex>\mathtt{minrun}</tex> играет немалое значение: при большом <tex>\mathtt{minrun}</tex> слияний будет меньше, а сортировки вставками будут выполняться долго. Причём эти функции растут с разной скоростью, поэтому и ещё после эксперементов на различных значениях и был выбран оптимальный диапазон {{---}} от <tex>32</tex> до <tex>64</tex>.