Сложность операции слияния в сортировке слияния

Question

Я читаю введение Кормена в алгоритмы.
Я не могу понять, почему слияние n/k массивов с k элементами в каждом из них имеет сложность O(n*log(n/k)).
Что мне здесь не хватает, так это то, что у нас есть n/k массивы. Поэтому нам необходимо выполнить слияние n/(k-1) раз с O(n) верхней границей.
Однако у нас есть логарифм, поэтому я полагаю, что мне не хватает чего-то в моем понимании сложности слияния.

Любая помощь приветствуется.

Answer 1

Предположим, вы только можете объединить два массива со слиянием (а, б), то вы можете построить «дерево» слияниях:

a b  c  d 
    ab   cd 
     abcd 

Теперь, это правда, что с помощью этой операции вы делаете на самом деле n/k - 1 слияния - но обратите внимание, что большинство из них выполняется с несколькими элементами, значительно меньше, чем n элементов на массив.

Если рассчитать его тщательно, вы получите:

2*(n/k)/2 * k + 2*(n/k)/4 * 2k + .... + 1*n 

Если вы алгебру, вы заметите, что это действительно n*log(n/k).

---

Как сторона не, другой способ сделать к-полосная слияния является держать кучу размером n/k, и пусть это держать наименьшее число из каждого массива, который еще не был исчерпан, и в то время как итерация - получить наименьший элемент в куче массива результатов.