Consider the following pseudocode for a sorting algorithm, for 0 < < 1 and n > 1 badSort(A[0... n-1]) if (n=2) and (A[0] >

Consider the following pseudocode for a sorting algorithm, for 0 < α < 1 and n > 1

badSort(A[0... n-1])

if (n=2) and (A[0] > A[1])

swap A[0] and A[1]

else if (n>2)

m = [α*n]

badSort(A[0... m-1])

badSort(A[n-m... n-1])

badSort(A[0...m-1])

4a. Show that the divide and conquer approach of badSort fails to sort the input array if α ≤ 1/2.

4b. Does badSort work correctly if α = 3/4? If not, why? Explain how you fix it.

4c. State a recurrence (in terms of n and α) for the number of comparisons performed by badSort.

4d. Let α= 2/3, and solve the recurrence to determine the asymptotic time complexity of badSort.