Problem 5 Professors Howard, Fine, and Howard have pro- posed the following "elegant" sorting algorithm STOOGE-SORT(A, i,j) then exchange A[i] then return D Round down 6 STOoGE-SorT(A, i,j k) 7 STOOGE-SorT(A, i + k,j) 8 STOOGE-SorT(A, i,j k) First two-thirds D Last two-thirds D First two-thirds again a. Let A- [10, 3,9,8, 1, 2,5, 7,6, 4]. Draw A after execution of (i) up to line 6, and (ii) up to line 7 in STOOGE-SORT(A, 1, 10) b. Argue that, if nlength|A], then STooGE-SORT(A, 1, n) correctly sorts the input array A[1.n]. Tip: use induction c. Give a recurrence for the worst-case running time of Stooge- Sort and a tight asymptotic (Theta-notation) bound on the worst-case run ning time. d. Compare the worst-case running time of Stooge-Sort with that of insertion sort, merge sort, heapsort, and quicksort