Question $6$: $20$ points

Professor Holmes has come up with a new sorting algorithm. He calls it Trinary Sort and

"claims" that it is asymptotically faster than Merge Sort, despite the fact both the algorithms

operate using similar logic. But, unlike Merge Sort, Trinary Sort splits the input array into

$($roughly$)3$ equal parts at each step of the recursion as long as the array is splittable $($i$.$e$.,$ has

at least $3$ elements$).$ Trinary Sort's merge subroutine, similar in principle to the one used by

Merge Sort, takes $3$ sorted subarrays and merges them to produce a single sorted array. Given

all of this, answer the following questions.

Page $4$ of $5$

$($a$)[4$ points$]$ In Merge Sort, the merge subroutine makes $n-1$ comparisons to merge $2$ arrays

of size $\frac{n}{2},$ which takes $(n)$ time. How many comparisons will the merge subroutine of

Trinary Sort make to merge $3$ arrays of size $\frac{n}{3}?$ What would be the $(cdots)$ bound on

the running time for this subroutine?

$($b$)[5$ points$]$ What is the $(cdots)$ bound on the running time of the Trinary Sort algorithm?

Come up with the answer using the Recursion Tree Method from class.

$($c$)[2$ points$]$ What is the recurrence relation for the Trinary Sort algorithm? Also explain it

in plain English what each term in the recurrence relation stands for.

$($d$)[4$ points$]$ What is the $\backslash$Theta $()$ bound on the running time of the Trinary Sort algorithm?

This time come up with the answer through Recurrence Relation Expansion of the

recurrence relation you came up with in part $($c$).$

$($e$)[5$ points$]$ Is Professor Holmes right to claim that Trinary Sort is asymptotically faster

than Merge Sort? Why$/$why not? Reason through your answer using a mathematical

proof.

$($Hint: Use the limit method demonstrated in class as well as the recitation on Asymptotic

Analysis & Recurrence Relations$)$