2-сторонние слияния наиболее эффективны при объединении блоков одинакового размера, поэтому наиболее эффективным слияниями k на основе 2-сторонних слияний является первое слияние блока 1 с блоком 2, блока 3 с блок 4 и т. д., затем объедините первые два результирующих блока и т. д. Это в основном то, как работает слияние, и приводит к времени O ( kn log k ), предполагая, что каждый из блоков k содержит n Предметы. Но он эффективен только в том случае, если все блоки имеют ровно n элементов, а k - это степень 2, поэтому ...
Вместо выполнения k отдельных проходов слияния вы можете использовать один проход, в котором используется куча, содержащая первый элемент каждого блока (т.е. всего k элементов):
- Чтение самого низкого элемента из кучи (время O (log k ))
- Запиши это
- вытащи его из кучи
- Если блок, из которого пришел этот предмет, еще не исчерпан, поместите следующий предмет из него в кучу (снова O (log k )).
- Повторяйте, пока куча не опустеет.
Если имеется всего kn элементов, это всегда занимает время O ( kn log k ) независимо от того, как они распределены среди блоков, и независимо от того, является ли k степенью 2. Ваша куча должна содержать (item, block_index)
пар, чтобы вы могли определить, из какого блока происходит каждый элемент.