Consider the following pseudocode for a sorting algorithm. StoogeSort(A[0 ... n - 1]) if n = 2 and A[0] > A[1] swap A[0] and A[1] else if n > 2 m = ceiling(2n/3) StoogeSort(A[0 ... m - 1]) StoogeSort(A[n - m ... n - 1]) Stoogesort(A[0 ... m - 1]) a) Verbally describe how the STOOGESORT algorithm sorts its input. b) Would STOOGESORT still sort correctly if we replaced k = ceiling(2n/3) with k = floor(2n/3)? If yes prove if no give a counterexample. (Hint: what happens when n = 4?) c) State a recurrence for the number of comparisons executed by STOOGESORT. d) Solve the recurrence to determine the asymptotic running time.