0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ You are giving no justification for the $O(n^2)$ behavior, except "I think". $\endgroup$
    – Yves Daoust
    Mar 13 at 8:12
  • $\begingroup$ There seems to be at least one word missing from the supposition. $\endgroup$
    – greybeard
    Mar 13 at 8:49
  • $\begingroup$ 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. $\endgroup$
    – gnasher729
    Mar 13 at 9:08

1 Answer 1

Reset to default
0
$\begingroup$

The linlogarithmic behavior of MergeSort is due to the fact that the size of the subsets decreases geometrically rather than arithmetically, so that the number of passes over the whole data is logarithmic.

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.

You get a similar situation when comparing dichotomic search and linear search in a sorted array.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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