Сортировка слиянием-вставкой

В информатике , сортировка слиянием-вставкой или алгоритм Форда-Джонсона представляет собой алгоритм сортировки сравнения опубликованный в 1959 году Л. Р. Фордом-младшим и Селмером М. Джонсоном . он использует меньше сравнений, В худшем случае чем лучшие ранее известные алгоритмы, двоичная сортировка вставкой и сортировка слиянием . и в течение 20 лет это был алгоритм сортировки с наименьшим количеством известных сравнений. Хотя это и не имеет практического значения, оно сохраняет теоретический интерес в связи с задачей сортировки с минимальным числом сравнений. Тот же алгоритм, возможно, был независимо открыт Станиславом Трибулой и Ченом Пингом.

Алгоритм

Сортировка слиянием-вставкой выполняет следующие шаги для входных данных: $X$ из $n$ элементы:

1. Сгруппируйте элементы $X$ в $\lfloor n/2\rfloor$ пары элементов произвольно, оставляя один элемент непарным, если количество элементов нечетное.
2. Выполнять $\lfloor n/2\rfloor$ сравнения, по одному на пару, для определения большего из двух элементов в каждой паре.
3. Рекурсивно сортировать $\lfloor n/2\rfloor$ более крупные элементы из каждой пары, создавая отсортированную последовательность $S$ из $\lfloor n/2\rfloor$ входных элементов в порядке возрастания.
4. Вставьте в начало $S$ элемент, который был в паре с первым и наименьшим элементом $S$.
5. Вставьте оставшиеся $\lceil n/2\rceil -1$ элементы $X\setminus S$ в $S$, по одному, со специально выбранным порядком вставки, описанным ниже. Используйте двоичный поиск в подпоследовательностях $S$ (как описано ниже), чтобы определить позицию, в которую должен быть вставлен каждый элемент.

Алгоритм разработан с учетом того факта, что двоичный поиск, используемый для вставки элементов в $S$ наиболее эффективны (с точки зрения анализа наихудшего случая), когда длина искомой подпоследовательности на единицу меньше степени двойки . Это связано с тем, что для этих длин все результаты поиска используют одинаковое количество сравнений друг с другом. Чтобы выбрать порядок вставки, обеспечивающий такую ​​длину, рассмотрим отсортированную последовательность $S$ после шага 4 схемы выше (перед вставкой остальных элементов),и пусть $x_{i}$ обозначают $i$th элемент этой отсортированной последовательности. Таким образом,

$S=(x_{1},x_{2},x_{3},\dots ),$

где каждый элемент $x_{i}$ с $i\geq 3$ сопряжен с элементом $y_{i}<x_{i}$ который еще не был вставлен. (нет элементов $y_{1}$ или $y_{2}$ потому что $x_{1}$ и $x_{2}$ были в паре друг с другом.) Если $n$ нечетно, оставшийся непарный элемент также должен быть пронумерован как $y_{i}$ с $i$ больше, чем индексы парных элементов.Затем последний шаг приведенной выше схемы можно расширить до следующих шагов:

• Разделить невставленные элементы $y_{i}$ на группы со смежными индексами. Есть два элемента $y_{3}$ и $y_{4}$ в первой группе, а суммы размеров каждых двух соседних групп образуют последовательность степеней двойки. Таким образом, размеры групп составляют: 2, 2, 6, 10, 22, 42,...
• Упорядочите невставленные элементы по группам (от меньших индексов к большим), но внутри каждой группы упорядочивайте их от больших индексов к меньшим. Таким образом, порядок становится

$y_{4},y_{3},y_{6},y_{5},y_{12},y_{11},y_{10},y_{9},y_{8},y_{7},y_{22},y_{21}\dots$

• Используйте этот порядок для вставки элементов $y_{i}$ в $S$. Для каждого элемента $y_{i}$, используйте двоичный поиск с начала $S$ до, но не включая $x_{i}$ чтобы определить, куда вставить $y_{i}$.

Анализ

Позволять $C(n)$ обозначают количество сравнений, которые делает сортировка слиянием-вставкой, в худшем случае, при сортировке $n$ элементы.Это количество сравнений можно разбить на сумму трёх слагаемых:

• $\lfloor n/2\rfloor$ сравнение пар предметов,
• $C(\lfloor n/2\rfloor )$ сравнения для рекурсивного вызова и
• некоторое количество сравнений для двоичных вставок, используемых для вставки остальных элементов.

В третьем члене наихудшее количество сравнений для элементов первой группы равно двум, поскольку каждое из них вставляется в подпоследовательность элементов. $S$ длиной не более трех. Первый, $y_{4}$ вставляется в трехэлементную подпоследовательность $(x_{1},x_{2},x_{3})$. Затем, $y_{3}$ вставляется в некоторую перестановку трехэлементной подпоследовательности $(x_{1},x_{2},y_{4})$, или в некоторых случаях в двухэлементную подпоследовательность $(x_{1},x_{2})$. Аналогично, элементы $y_{6}$ и $y_{5}$ второй группы каждый вставляется в подпоследовательность длиной не более семи с использованием трех сравнений. В более общем смысле, наихудшее количество сравнений элементов в $i$эта группа $i+1$, поскольку каждая из них вставляется в подпоследовательность длиной не более $2^{i+1}-1$. Суммируя количество сравнений, использованных для всех элементов, и решая полученное рекуррентное соотношение ,этот анализ можно использовать для расчета значений $C(n)$, давая формулу

$C(n)=\sum _{i=1}^{n}\left\lceil \log _{2}{\frac {3i}{4}}\right\rceil \approx n\log _{2}n-1.415n$

или, в закрытом виде ,

$C(n)=n{\biggl \lceil }\log _{2}{\frac {3n}{4}}{\biggr \rceil }-{\biggl \lfloor }{\frac {2^{\lfloor \log _{2}6n\rfloor }}{3}}{\biggr \rfloor }+{\biggl \lfloor }{\frac {\log _{2}6n}{2}}{\biggr \rfloor }.$

Для $n=1,2,\dots$ количество сравнений

0, 1, 3, 5, 7, 10, 13, 16, 19, 22, 26, 30, 34, ... (последовательность A001768 в OEIS )

Связь с другими видами сравнения

Алгоритм называется сортировкой вставкой слиянием, потому что первоначальные сравнения, которые он выполняет перед рекурсивным вызовом (объединение произвольных элементов в пары и сравнение каждой пары), такие же, как и начальные сравнения сортировки слиянием .в то время как сравнения, которые он выполняет после рекурсивного вызова (используя двоичный поиск для вставки элементов один за другим в отсортированный список), следуют тому же принципу, что и сортировка вставкой . В этом смысле это гибридный алгоритм , сочетающий в себе сортировку слиянием и сортировку вставкой.

Для небольших входов (до $n=11$) его количество сравнений равно нижней границе сортировки сравнения $\lceil \log _{2}n!\rceil \approx n\log _{2}n-1.443n$. Однако для больших входных данных количество сравнений, выполняемых алгоритмом вставки слиянием, превышает эту нижнюю границу.Сортировка вставкой слиянием также выполняет меньше сравнений, чем сортировка чисел , которая подсчитывает сравнения, выполненные при двоичной сортировке вставкой или в худшем случае сортировке слиянием. Числа сортировки колеблются между $n\log _{2}n-0.915n$ и $n\log _{2}n-n$, с тем же ведущим членом, но с худшим постоянным множителем в линейном члене более низкого порядка.

Сортировка слиянием-вставкой — это алгоритм сортировки с минимально возможным сравнением для $n$ предметы всякий раз, когда $n\leq 22$, и у него наименьшее количество сравнений, известных для $n\leq 46$. В течение 20 лет сортировка слиянием-вставкой была алгоритмом сортировки с наименьшим количеством сравнений, известных для всех входных длин.Однако в 1979 году Гленн Манахер опубликовал другой алгоритм сортировки, который использовал еще меньше сравнений для достаточно больших входных данных. Остается неизвестным, сколько именно сравнений необходимо для сортировки, для всех $n$, но алгоритм Манахераи более поздние рекордные алгоритмы сортировки использовали модификации идей сортировки вставкой слиянием.