Consider a modified version of Mergesort algorithm, which works as follows.

if the array has less than $3$ elements, then we sort it trivially

otherwise, we

recursively sort the first third of the array

recursively sort the second third of the array

recursively sort the final third of the array

merge the first third with the second third

merge the first two$-$third with the final third

return thef$$nal merged array

Which of these best captures the recurrence for the running time of the above algorithm? You may ignore floors and ceilings or assume that the size of array is a power of $3.$

$T(n)=3T(\frac{n}{3})+n$

$T(n)=2T(\frac{n}{2})+n$

$T(n)=3T(\frac{n}{2})+n$

$T(n)+3T(\frac{n}{3})+n^2$