9.3-3

Show how quicksort can be made to run in O(n lg n) time in the worst case, assuming that all elements are distinct.
The worst case for quick sort occurs when the split creates 0 and n-1 elements. $T(n) = T(n-1)+\theta(n)$. But if we select a median that gives us n/2 and n/2 split always then we can eliminate the worst case.
BEST-CASE QUICKSORT(A,p,r)
if p < r then $$i \leftarrow (r-p+1)/2 $$ $$ x \leftarrow SELECT(A,i)$$ $$ q \leftarrow PARTITION(A,x)$$ BEST-CASE QUICKSORT(A,p,q-1)
BEST-CASE QUICKSORT(A,q+1,r)
Because the BEST-CASE QUICKSORT recurses only on elements of size at most n/2(for even n n/2 and n/2 - 1 and for odd n n/2 and n/2). $$T(n) \leq 2 T(n/2) + \theta(n)$$ The running time for above recursion is similar to merge sort $O(n log n()$