Merge sort algorithm

Question

Consider the modified merge sort where we divide array into 5 equal sub arrays instead if 2(as in standard merge sort).What is the time complexity if modified merge sort? Is there any improvement over standard merge sort?

Comments

O(nlogn)

---

The array is divided into 5 parts and all parts are equal so the recurrence relation will be

5T(n/5) + n

On solving this will be O(nlogn).

---

Dividing n into 5 parts of n/5 each is no doubt going to reduce the height of the tree and from this we might think that since height of the tree is reduced , so it's complexity is also going to reduce. But..... As of now We don't have a merge procedure which can merge 5 subparts into one part in linear time. That's where the idea is Lacking its Strength.

Answer 1

if we want to divide the array in 5 sub array then  recurrence relation become

T(n) =5T(n/5)+n.

it will also take o(nlogn) which is asymptotically equal.

Comments

Then why do we divide in 2? I think dividing in size of 5 will have more time complexity by some constant factor.I am looking what that constant factor is?

One more thing:- You have taken time to merge as 'n',so is it possible to merge 5 sub arrays of size (n/5)  in n?

---

If we divide array more and more, will merge sort be better?

Is it improve efficiency?

I donot think so.

If there are n elements and divide the merge sort with n element, then will mersort work at all?

I donot think so.

So, no of division is more, merge sort will be less efficient I think

---

If we increase the number of division of array then I think there is no change in the time Complexity because at any point of time we can apply merge procedure over only two subarrays. which take O(n) time thus in our standard merge sort algorithm we have $n$ which denotes the time required to perform merge procedure.