NPTEL Assignment Question

Question

Suppose we do merge sort with a three-way split: divide the array into 3 equal parts, sort each part and do a 3 way merge.

What would the worst-case complexity of this version be?

 

• A. O($n^2$)
• B. O($n^2$ log3n)
• C. O(n log2n)
• D. O(n $(log2n)^2$)  

Comments

Hi, In the option C, is that log base 2? If it is then it should be the answer.

Answer 1

C. O(n log2n) ...

 

# A variant of merge sort is called 3-way merge sort where instead of splitting the array into 2 parts we split it into 3 parts…

 

  ##  Merge sort recursively breaks down the arrays to subarrays of size half...

 

###  Similarly, 3-way Merge sort breaks down the arrays to subarrays of size one third...

 

1. https://en.wikipedia.org/wiki/Merge_sort