What will be the complexity of given modified merge sort

Question

Shiva modified merge sort as:

1. divide the array into 3 equal parts insttead of 2.
2. sort each part
3. do a 3 way merge.

What can we conclude about modified  three way  merge sort?

A. It has same worst case complexity as normal merge sort 

B. It has less complexity as comparisons reduces to log 3 level.

C. It is more complex due to 3 way merge

D. The algorithm will not work perfectly for some inputs.

Answer 1

answer should be A

the recurrence relation will be of this form

T(N)=3T(N/3)+O(N)

by masters theorem it is O(NLOGN)

Comments

Your concpet is very correct. But a smalle clarification.
In modified  3 way merge sort,

T(N)=3T(N/3)+O(N) // 3T(N/3) is to divide the array and O(N) to merge elements, that are multiple of 3.

Thus by Masters' theorem , final answer will be

  O(NLOG ₃ N) 

But N LOG ₃ N = N (log ₂  N / log ₂  3)  = 2.09 (N log ₂ N) > N LOG ₂ N

Thus 3 way merge sort is slower than 2 way merge sort

Answer will be C

---

as O(nlog3n) is O(2.09 *N log 2 N), if we consider this 2.09 as constant,

then would this become O(c*nlog2n) which is same as O(nlog2n)

Answer 2

Answer should be A,C

FOR ANSWER A

T(N)=3T(N/3)+O(N) time complexity is O(n*log(n)).

FOR ANSWER C

we are dividing element in to three part means increasing divide operation and  perform divide operation is complex.by asymptotic both are take  same  time but by constant it will take more time as compared to original merge sort.It is more complex due to 3 way merge