Stack depth for QuickSort: The QuickSort algorithm we described contains two recursive calls. Compilers usually execute recursive procedures by using a stack that contains pertinent information (that includes the parameter values) called stack frame, for each recursive call. The information for the most recent call is at the top of the stack, and the information for the initial call is at the bottom. When a procedure is invoked, its stack frame is pushed onto the stack; when it terminates, its stack frame is popped. Lets assume we want to sort array A[1..n]. The stack frame corresponding to a subarray to be sorted is the pair of extreme indices of that subarray, and takes O(1) memory cell space. The stack depth is the maximum number of stack frames on the stack at any time during the computation.

a) Describe a scenario in which the stack depth for QuickSort, as described in the course, is Theta(n).

b) Modify the code for QuickSort so that the worst-case stack depth is Theta(log n). You must maintain the O(n log n) expected running time of the algorithm.

You must give a convincing proof of the improved bound on stack depth.

[Hint: decide which of the 2 recursive calls to invoke first.]