Многократное слияние против двухстороннего слияния

Question

Когда мы внешне объединяем сортировку большого файла, мы разделяем его на маленькие, сортируем и затем объединяем обратно в большой отсортированный файл.

При слиянии мы можем сделать много проходов двухстороннего слияния или одно многократное слияние.

Мне интересно, какой подход лучше? и почему?

Answer 1

Одно многоплановое слияние обычно лучше. Рассмотрим три небольших файла:

a1
a2
a3

а также

b1
b2
b3

и наконец

c1
c2
c3

Если вы делаете слияние с a а также bмы остались с (скажем)

a1
b1
a2
b2
b3
a3

а также

c1
c2
c3

Окончательное слияние создаст отсортированный список, но обратите внимание, что в этом последнем слиянии мы должны посетить a а также b предметы снова. Именно это повторное слияние бесполезно при каскадном двустороннем слиянии.

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