Silly-Sort Consider the following sorting algorithm Silly-Sort(A,i,j) if A[i] > A[j] then exchange A[i] and A[j]; if i+1 >= j then return; k = floor((j-i+1)/3); Silly-Sort(A,i,j-k); Silly-Sort(A, i+k,j); Silly-Sort(A,i,j-k); (a) Argue (by induction) that if n is the length of A, then Silly- Sort(A,1,n) correctly sorts the input array A[1...n] (b) Give a recurrence relation for the worst-case run time of Silly-Sort and a tight bound on the worst-case run time (c) Compare this worst-case runtime with that of insertion sort, merge sort, heapsort and quicksort