I'm reading Cormen's Introduction into algorithms.
I can't understand why merging n/k arrays with k elements in each of them has the complexity of O(n*log(n/k)).
What I'm missing here is that we have n/k arrays. Therefore, we have to perform the merge n/(k-1) times each with O(n) upper-bound.
However we have a logarithm, so I suppose that I'm missing something in my understanding of Merge complexity.
Any help is welcome.
Assume you only can merge two arrays with merge(a,b), then you can build a "tree" of merges:
a b c d
ab cd
abcd
Now, it is true that using this operation you are doing indeed n/k - 1 merges - but note that most of them are done with few elements, significantly less than n elements per array.
If you calculate it carefully, you'll get:
2*(n/k)/2 * k + 2*(n/k)/4 * 2k + .... + 1*n
If you do the algebra, you'll note that this is indeed n*log(n/k).
As a side not, another way to do k-way merge is to hold a heap of size n/k, and let it hold the smallest number from each array that was not exhausted yet, and while iterating - get the smallest element in the heap to the result array.