0
$\begingroup$

As in, with the two final sublists which are sorted arrays, let's say just for this example (yes it is no longer fully MergeSort but I am interested in the time complexity only), that we finish with a constant time operation involving the two sublists. MergeSort in worst case is $O(n\log(n))$, and not having the final merge would definitely lead to greater efficiency than this, but by how much? Again, I understand that MergeSort has not completed it's full run, I am only interested with its time complexity for my specified run only.

$\endgroup$
2
$\begingroup$

It will still take $O(n \log n)$.

There are four steps in mergesort.

  1. Divide the list in half.
  2. Mergesort the left half.
  3. Mergesort the right half.
  4. Merge the two together.

If I understand right, you're asking about removing the fourth step, in the final stage only (that is, not in any of the recursive calls).

In this case, you'll still have to do step 1 in $O(1)$, step 2 in $O(\frac{n}{2} \log \frac{n}{2})$, and step 3 in $O(\frac{n}{2} \log \frac{n}{2})$ (since steps 2 and 3 still call conventional mergesort, which is $O(n \log n)$).

So your total time complexity will be $O(1 + \frac{n}{2} \log \frac{n}{2} + \frac{n}{2} \log \frac{n}{2}) = O(n \log \frac{n}{2}) = O(n \log n)$.

The final merging only takes $O(n)$ time; it's the recursive part that's the real cost.

$\endgroup$
  • $\begingroup$ Would it still achieve even better efficiency just by a slight bit still? $\endgroup$ – Azxdreuwa May 27 '18 at 6:15
  • 1
    $\begingroup$ @Azxdreuwa In practice you'd get a bit, but asymptotically nothing. It's far outweighed for large $n$ by the cost of the recursive algorithm. $\endgroup$ – Draconis May 27 '18 at 6:32

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.