# $m-$way merge sort, extended merge sort

Consider Merge-sort algorithm that we modify as follow:

Suppose we extend it to divide the input array into $$m$$ not necessary equal and after sorting each of them, merge them. Now can we conclude that the running time will be $$O(n\log n)$$?

I think the running time should be $$O(n^2)$$ as follow:

If the algorithm divide to three sections such that two first sections contains some constant number of elements and third sections contains all most elements then the running time will be $$O(n^2)$$ if the algorithm continue dividing as mentioned scenario.

• You are giving no justification for the $O(n^2)$ behavior, except "I think". Mar 13 at 8:12
• There seems to be at least one word missing from the supposition. Mar 13 at 8:49
• Yes, if I split n numbers into 1 / 1 / n-2 numbers then the runtime will be Theta(n^2). But that would be utterly stupid. Mar 13 at 9:08

You might very well roll a modified MergeSort that subdivides in fractions $$\frac12,\frac13,\frac16$$ and keep the same complexity.
But if we pursue your idea of handling subarrays of constant size, the archetypal algorithm that you obtain is StraightInsertionSort (recursively split $$n$$ in $$n-1$$ and $$1$$ sizes), that notoriously has an $$O(n^2)$$ behavior, because the number of passes is linear.