Question $1.(20$ marks$)$ Consider the algorithm $LpySort(A,l,r)$ below, where $A[1..n]$ is an array,

and $1lrn.$ This is a recursive sorting algorithm that $($unlike Mergesort$)$ requires no merging and

$($unlike Quicksort$)$ requires no partitioning.

a$.$ Prove that a call to LOOPySort $(A,l,r)$ sorts the subarray $A[l..r]$ in increasing order. To simplify

matters, you may assume that the length $r-l+1$ of $A[l..r]$ is a power of $3.$

b$.$ Use the Master Theorem to determine the running time $T(n)$ of the call $\frac{L}{o}O$ PySort$(A,1,n).$

c$.$ How does the running time of $LpySort(A,1,n)$ compare to the running time of Bubblesort on

array $A[1..n]?$ Justify your answer.