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

В Информатика, сортировка слиянием и вставкой или Алгоритм Форда – Джонсона это сравнительная сортировка алгоритм, опубликованный в 1959 г. Л. Р. Форд-младший и Селмер М. Джонсон.^[1][2][3][4] Он использует меньше сравнений в худший случай чем лучшие ранее известные алгоритмы, сортировка двоичной вставкой и Сортировка слиянием,^[1] и в течение 20 лет это был алгоритм сортировки с наименьшим количеством известных сравнений.^[5] Хотя это и не имеет практического значения, он остается теоретическим интересом в связи с проблемой сортировки с минимальным числом сравнений.^[3] Тот же алгоритм мог быть независимо открыт Станислав Трыбула и Чен Пинг.^[4]

Алгоритм

Сортировка слиянием и вставкой выполняет следующие шаги на входе ${\displaystyle X}$ из ${\displaystyle n}$ элементы:^[6]

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

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

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

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

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

${\displaystyle 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 }$

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

Анализ

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

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

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

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

или в закрытая форма,^[8]

${\displaystyle 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 }.}$

За ${\displaystyle n=1,2,\dots }$ количество сравнений^[1]

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

Отношение к другим видам сравнения

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

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

Сортировка слиянием и вставкой - это алгоритм сортировки с минимально возможным сравнением для ${\displaystyle n}$ предметы, когда ${\displaystyle n\leq 15}$ или же ${\displaystyle 20\leq n\leq 22}$, и он имеет наименьшее количество сравнений, известных для ${\displaystyle n\leq 46}$.^[10][11]В течение 20 лет сортировка слиянием-вставкой была алгоритмом сортировки с наименьшим количеством сравнений, известных для всех входных длин. Однако в 1979 году Гленн Манахер опубликовал другой алгоритм сортировки, который использовал еще меньше сравнений для достаточно больших входных данных.^[3][5]Остается неизвестным, сколько именно сравнений необходимо для сортировки для всех ${\displaystyle n}$, но алгоритм Манакера и более поздние алгоритмы сортировки, побившие все рекорды, использовали модификации идей сортировки слиянием и вставкой.^[3]

Рекомендации

1. Форд, Лестер Р. мл.; Джонсон, Селмер М. (1959), «Турнирная задача», Американский математический ежемесячный журнал, 66: 387–389, Дои:10.2307/2308750, МИСТЕР  0103159
2. Уильямсон, Стэнли Гилл (2002), «2.31 Вставка слияния (Форд – Джонсон)», Комбинаторика для компьютерных наук, Дуврские книги по математике, Courier Corporation, стр. 66–68, ISBN  9780486420769
3. Махмуд, Хосам М. (2011), «12.3.1 Алгоритм Форда – Джонсона», Сортировка: теория распределения, Ряд Уайли по дискретной математике и оптимизации, 54, John Wiley & Sons, стр. 286–288, ISBN  9781118031131
4. Кнут, Дональд Э. (1998), «Вставка слияния», Искусство программирования, Vol. 3. Сортировка и поиск (2-е изд.), С. 184–186
5. Манахер, Гленн К. (июль 1979 г.), "Алгоритм сортировки Форда-Джонсона не оптимален", Журнал ACM, 26 (3): 441–456, Дои:10.1145/322139.322145
6. Оригинальное описание Форд и Джонсон (1959) отсортировал элементы в порядке убывания. Перечисленные здесь шаги обращают вывод, следуя описанию в Кнут (1998). Результирующий алгоритм выполняет те же сравнения, но вместо этого выдает порядок возрастания.
7. Кнут (1998) приписывает формулу суммирования доктору философии 1960 г. диссертация А. Хадиана. Формула аппроксимации уже была дана Форд и Джонсон (1959).
8. Гай, Ричард К.; Новаковски, Ричард Дж. (Декабрь 1995 г.) "Ежемесячно Нерешенные проблемы 1969–1995 », Американский математический ежемесячный журнал, 102 (10): 921–926, Дои:10.2307/2975272
9. Кнут (1998), п. 184: «Поскольку он включает в себя некоторые аспекты слияния и некоторые аспекты вставки, мы называем это вставка слияния."
10. Peczarski, Marcin (2004), "Новые результаты в сортировке с минимальным сравнением", Алгоритмика, 40 (2): 133–145, Дои:10.1007 / s00453-004-1100-7, МИСТЕР  2072769
11. Peczarski, Marcin (2007), "Алгоритм Форда-Джонсона все еще непревзойден для менее чем 47 элементов", Письма об обработке информации, 101 (3): 126–128, Дои:10.1016 / j.ipl.2006.09.001, МИСТЕР  2287331