Let mixsort$($A$,1,$ n$)$ be an algorithm that sorts an array A with n

integers. It works as follows:

mixsort$($A$,$ p$,$ q$)\{$

if p $>=$ q$,$ return;

r$=$partition$($A$,$ p$,$ q$)$;

$//$run mixsort on the low part

mixsort$($A$,$ p$,$ r $1)$;

$//$run insert sort on the high part

insertsort$($A$,$ r $+1,$ q$)$;

$\}$

Compute the best$-$case, worst$-$case, and average$-$case complexities of mixsort.