Question 2 - 10 points

Consider the following modification to the merge sort algorithm: divide

the input array into thirds (rather than halves), recursively sort each third, and

finally combine the results using a three-way Merge subroutine. What is the

running time of this algorithm as a function of the length n of the input array,

ignoring the constant factors and lowest order terms? (provide explanation and

working details)