Question

prove it's correct or not.

A particular version of MERGESORT breaks the array into three equal parts, recursively sorts the first two parts, merges them, recursively sorts the last part, and merges it with the already merged parts one and two. This MERGESORT has the same worst-case running time as the standard version.

Answer 1

Yes It's correct the merge sort that you mentioned is called as 3 - way Merge Sort has same worst-case running time as the standard 2 way merge sort .

Proof :

We can do Proof using how to build recurrence Relation for both standard and 3 way merge sort and then we can see that after solving we get same complexity or not

In Normal merge sort we have

1. Divide array into halves

2. Sort those halves

3. Merge It

Here Merge takes O(n) time

We get Recurrence Relation as

T(n) = 2 T ( n/2 ) + n  

Now Similarly we have 3 way merge sort

Steps

1. We divide array in 3 parts where each part has n/3 elements

2. Now we sort first two and merge them

3. Then we sort the third part and merge with it with merged part we get in Step 2

Here Lets see how we can build similar Recurrence Relation

The running time to merge first two parts is n/3 + n/ 3 for the call to Merge(L1,L2) = 2n/3

Now we are merging n/3 and 2n/3 so time needs for Merge ( Merge(L1,L2) , L3 )   =

Hence Total time = 5n/3 = same as O(n)

So we get recurrence relation is

T(n) = 3 T( n/3 ) + n

Now We can solve it using Master Theorem

we have n^log₃3 = n = f(n)

So it is case 3 of the Master Theorem

Hence we get Time complexity as O ( nlogn ) which is same as standard merge sort .

This is how we can proof how 3 way merge sort has same complexity of O( nlogn)

If u like the answer do Upvote it and have any doubt ask in comments

Thank You