Если у вас есть n (n> 2) списков, то это неправда, что вам нужно проводить (n-1) сравнения на каждом шаге слияния. Однако реализация становится более сложной.
Предположим, у вас есть три списка list[0..2], и для простоты предположим, что вы объединяете их, и они все еще не пусты (т. Е. Вы не дошли до конца ни одного из списков). Кроме того, для простоты предположим, что все элементы различны, то есть, когда вы сравниваете два элемента, они никогда не совпадают. Тогда у вас есть шесть возможных «состояний», в которых вы можете находиться, которые соответствуют шести перестановкам трех списков в порядке возрастания первых элементов в списках, т.е. если
list[0] = [5, 7, 11, 15]
list[1] = [3, 4, 20, 21]
list[2] = [9, 10, 12, 19]
тогда соответствующая перестановка списков равна [1, 0, 2], то есть list[1] имеет наименьший передний элемент, а list[2] имеет наибольший передний элемент.
Когда вы выталкиваете следующий элемент (4) из list[1], вы уже знаете, что list[0].front <<code>list[2].front в зависимости от состояния [1, 0, 2], где вы были. Так что теперь вам нужно выполнить 1 или 2 сравнения:
if (list[1].front < list[0].front) // (A)
--> move to state [1, 0, 2], next to pop is list[1]
else if (list[1].front < list[2].front)
--> move to state[0, 1, 2], next to pop is list[0]
else
--> move state[0, 2, 1], next to pop is list[0]
Предполагая некоторую однородность, вероятность того, что сравнение (A) вернет истину, то есть, что следующий элемент в списке, из которого вы удалили предыдущий элемент, меньше, чем наименьший элемент в двух других списках, равен 1 / 3, то есть в среднем (1/3 x 1 + 2/3 x 2) = 5/3 сравнений вместо 2 (что будет n-1).
Это, очевидно, хуже на 2/3 сравнений на одну вставку с обычной сортировкой слиянием, для которой требуется только 1 сравнение на извлеченный элемент.
Мы можем получить лучший результат, рассматривая также частично упорядоченные состояния. Существует три различных сравнения (список [0] - список [1], список [1] - список [2] и список [0] - список [2]). Если мы допустим, чтобы известные результаты (<,>) были дополнены "не знаю" (?), Возможны следующие состояния:
0/1 1/2 0/2
< < < (total order) [0,1,2]
< ? < (0 is least but don't know if 1 < 2) [0,1,2] [0,2,1]
< ? ? (0 is < 1, but 2 can't be positioned) [2,0,1] [0,2,1] [0,1,2]
? ? ? (no information about ordering) (all six permutations)
а затем все варианты, касающиеся перестановок и замены в разных местах матрицы.
Теперь, если вы были в состоянии (<, <, <) (предположим, [0,1,2]), и вы читаете следующий элемент из списка, из которого вы открыли предыдущий, есть два случая: либо ( 1) вы получаете элемент, который меньше, чем элемент в списке [1], и в этом случае вы возвращаетесь в состояние [0,1,2] в одном сравнении; или вы получите элемент, который выше, чем элемент в списке [1]. В этом случае вы можете вывести list [1] далее, и вы вошли в состояние (<,?, <): Вы знаете, что list [1] имеет наименьший передний элемент, но не знаете сейчас, если list [0] или список [2] следующий. </p>
Теперь в состоянии (<,?, <) Вы читаете новый элемент из списка [1], вы можете использовать сравнения 1 + (1/3 + 4/3) = 1 5/3, чтобы найти фактическую перестановку. из всех списков, и вы вернетесь в (<, <, <) состояние. Таким образом, эта последовательность из двух нажатий стоит 2 5/3 сравнений, в среднем 1 5/6 = 11/6 на вставку; однако из-за возможности того, что вы можете вставить два самых младших элемента в последовательность из одного и того же списка, средняя стоимость еще меньше, по тому же аргументу, что и раньше (1/3 + 2/3 x 11/6) = 6 / 18 + 22/18 = 1 + 5/9, хуже, чем исходная сортировка слиянием на 5/9 сравнений на одну вставку, но немного лучше, чем на 2/3 выше. </p>
Для полноты приведем алгоритм (фрагмент показан):
state_1_lt_2: /* known list[1].front < list[2].front */
if (list[0].front < list[1].front):
merge_from(0)
goto state_1_lt_2 /* 1 insert 1 comp prob 1/3 */
else
merge_from(1)
if (list[0].front < list[1].front)
if (list[1].front < list[2].front)
merge_from(0)
goto state_1_lt_2 /* 2 inserts 3 comps prob 2/3*1/2*1/3 = 1/9 */
else if (list[0].front < list[2].front)
merge_from(0)
goto state_2_lt_1 /* 2 inserts 4 comps prob 2/3*1/2*2/3*1/2 = 1/9 */
else
merge_from(2)
goto state_0_lt_1 /* 2 inserts 4 comps prob 1/9 */
else if (list[2].front < list[1].front)
merge_from(2)
goto state_1_lt_0 /* 2 inserts 3 comps 2/3 x 1/2 x 1/3 = 1/9 */
else if (list[2].front < list[0].front)
merge_from(1)
goto state_2_lt_0 /* 2 inserts 4 comps prob 1/9 */
else
merge_from(1)
goto state_0_lt_2 /* 2 inserts 4 comps prob 1/9 */
Суммирует ожидаемое количество сравнений на одну вставку
.
1/3 x 1 + 4/9 x (4/2) + 2/9 x (3/2) = 6/18 + 16/18 + 6/18 = 30/18 = 1 5/9.