Why is time complexity of k-way merge sort O(nk^2)?

Question

I'm comparatively new to algorithm analysis and am taking a related course on coursera where I came accross k way merge sort.

The time complexity of 2 way merge sort is n log2 n, of 3 way merge sort is n log3 n and of 4 way merge sort is n log4 n.

But, in the case of k-way the complexity is nk^2. This is because we pay attention to the merge part of the algo; (2n + 3n + 4n...kn).

But, in case of 2, 3 and 4-way algorithms, we pay attention to the recursive call of one function; (2T(n/2) + c.n).

Can anybody please explain why this is so? Or correct my approach to this question.

Answer 1

the recursion depth is log n/log k,

merging costs n*log k, using a min heap for log k per element

thus we come at T(n) = n* log k + K* T(n/k) which (unless I'm mistaken) becomes n log n (actually n (c_1/k+log(n))= n/k + n*log(n) but the n/k becomes insignificant in big O)

Answer 2

I'm pretty sure the complexity of k way merge sort is O(knlog_k(n)) not O(nk^2) without implementing other algorithms or data structures. O(kn) per step of the algorithm, and log_k(n) steps. Doubt you still need an answer tho since it has been seven years...