Если все, что вас волнует, это количество записей массива, вторая версия (трехстороннее объединение) работает быстрее, чем первый алгоритм (два случая двухстороннего объединения).Алгоритм трехстороннего слияния будет выполнять ровно 3n записей (где n - длина любой из последовательностей), поскольку он объединяет все три диапазона за один проход.Первый подход объединит два диапазона вместе, выполняя запись 2n, а затем объединит эту последовательность с третьей последовательностью, выполнив запись 3n для общей суммы записи 5n.
В общем, предположим, что у вас естьk диапазонов элементов, все длины n.Если вы объединяете эти диапазоны попарно, затем объединяете эти объединения попарно снова и т. Д., То вы будете делать примерно k / 2 шагов объединения, объединяя диапазоны длины n, затем k / 4 объединяет диапазоны длины 2n, затем k / 8 объединяетдлина 4n и т. д. Это дает сумму
kn / 2 + kn / 2 + ... + kn / 2 (log n times)
Для чистого числа записей массива, которыеO (kn lg n).Если, с другой стороны, вы используете k-way сравнение на каждом шаге, вы делаете именно kn записи, что намного меньше.
Теперь давайте подумаем о том, сколько сравнений вы делаете в каждой настройке.При трехстороннем слиянии каждый элемент, записанный в выходную последовательность, требует нахождения как минимум трех значений.Это требует двух сравнений - одно для сравнения первых значений первых двух последовательностей, и одно для сравнения минимума этих двух значений с первым значением третьего массива.Таким образом, для каждого значения, записанного в результирующую последовательность, мы используем два сравнения, и поскольку записано 3n значений, нам нужно сделать не более 6n сравнений.
Намного лучший способ сделать этохранить последовательности в минимальной куче, где последовательности сравниваются по их первому элементу.На каждом шаге мы снимаем последовательность с кучи с наименьшим первым значением, записываем это значение в результат, затем помещаем оставшуюся часть последовательности обратно в кучу.Для k последовательностей это означает, что для каждого записанного элемента требуется не более O (lg k) сравнений, поскольку вставка кучи выполняется за O (lg k).Это дает чистое время выполнения O (kn lg k), поскольку для каждого из записанных элементов kn требуется время обработки O (lg k).
В другой версии мы начинаем со стандартного двустороннего взаимодействия.объединение, для которого требуется одно сравнение на каждый записанный элемент, итого всего 2n сравнений.Во втором проходе слияния, в худшем случае мы делаем 3n сравнений, так как объединяются элементы 3G.Это дает в общей сложности 5n сравнений.Если мы используем обобщенную конструкцию для парного слияния, которая описана выше, нам нужно будет использовать O (kn lg n) сравнений, поскольку каждый записанный элемент требует одного сравнения, а мы делаем O (kn lg n) записей.
Короче говоря, для конкретного случая k = 3 мы имеем, что трехстороннее слияние выполняет 3n операций записи и 6n сравнений для сети из 9n операций чтения и записи в память.Повторное двустороннее слияние выполняет 5n операций записи и 5n сравнений, что дает в общей сложности 10n операций чтения и записи в память, поэтому версия с тремя способами слияния лучше.
Если мы рассмотрим обобщенные конструкции, то k-way merge выполняет O (nk) записи и O (nk lg k) сравнений для всего O (nk lg k) операций с памятью.Итеративный алгоритм двустороннего слияния выполняет O (nk lg n) операций записи и O (nk lg n) сравнений для всего O (nk lg n) операций с памятью.Таким образом, k-way merge асимптотически лучше для нескольких длинных последовательностей, в то время как повторная сортировка слиянием быстрее для многих коротких последовательностей.
Надеюсь, это поможет!