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.

2 Answers 2


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)


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...

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.