Advantage of 2-way merge sort against n-way

Question

It's known 2-way Merge sort takes N*logN time.

I wonder, what would be the running time if we split an array of the size N into N subarrays and then do the same thing as we would do for 2-way Merge?

Answer 1

Well, the recurrence will be:

where f(n) is the merge function.

Of course in 2-way merge sort we can do this in linear time, hence f(n)=O(n) for the k=2 case. But in general, the best time this can be done is O(nlogk), using Priority Queues.

Now, according to the Master Theorem you can solve this recurrence and see that T(n)=O(n log n).

So in asymptotic notation it looks like both k-way and the original merge-sort are equal. however note that in practice, implementing the original merge-sort is simpler and might require less effort to implement and maintain.