NewSort$($A$,$ p$,$ r$)$

n $=$ r $-$ p $+1$

if $($n $<=10)$

then

InsertionSort$($A$,$ p$,$ r$)$

else

k $=$n$/3$

NewSort$($A$,$ p$,$ r $-$ k$)$

NewSort$($A$,$ p $+$ k$,$ r$)$

NewSort$($A$,$ p$,$ r $-$ k$)$

a$)$ Explain why, after calling NewSort$($A$,1,$ n$),$ the array A would be sorted from $1$ to n$.$ Your explanation does not need to be formal, just enough to convince the professor.

b$)$ Write the recurrence that describes the algorithm's runtime and solve it$.$ The floor and ceiling functions should be very precise.

c$)$ Comment on the following statement: if the InsertionSort from line $3$ were replaced by MergeSort, the asymptotic behavior of the function would improve.