Question 5: Consider the following recursive algorithm: Algorithm Weirdsort(A[0 . . . n - 1]): if n = 2 and A[0] > A[1]: swap A[0] A[1] else if n > 2: m - [2n/3]; Weirdsort(A[0 . . . m - 1]) Weirdsort(An - m. . . n - 1]) Weirdsort( A[0 . . . m - 1]) (a) Prove that Algorithm Weirdsort correctly sorts the elements in the array A. (b) Ignoring ceilings (i.e. we can assume that n is a power of 3), write the recurrence in terms of n describing how many calls are made to Weirdsort with an initial call of Weirdsort(A[0 . . . n - 1])? Hint: write a recurrence whose general form is R(n) = aR(n/b) + f(n) where a, b are rational numbers and f(n) is a function of n. Justify why your recurrence is counting the number of recursive calls. (c) Using this recurrence, prove that R(n) is at most n' when n 2 2 using induction