$(15$ pts$,$ standard$)$ StupidSort is a sorting algorithm that I invented last

night. It can sort an array of $n$ integers in worst case as well as average case

time $O(n^3).$ We also know that partition is a procedure, with return value

$r,$ that reorganizes an array of $n$ integers and splits the reorganized array

into a low$-$part and a high$-$part, separated by the element indexed by $r.$ Let

mixsort $(A,1,n)$ be an algorithm that sorts an array A with $n$ integers. It

works as follows:

if $pq,$ return;

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

$//$run mixsort on the low part

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

$//$run StupidSort on the high part

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

$\}$

Compute the average$-$case time complexity of mixsort. Please faithfully fol$-$

low the steps of "write a formula", "guess a solution" $($Try to guess $O(n^3)),$

and "check your solution" and show your math work.