Reference no: EM131662311

Question: Suppose that the recursive quicksort receives an int parameter, depth, from the driver that is initially approximately 2 log N.

a. Modify the recursive quicksort to call mergeSort on its current subarray if the level of recursion has reached depth. (Hint: Decrement depth as you make recursive calls; when it is 0, switch to mergesort.)

b. Prove that the worst-case running time of this algorithm is O(N log N).

c. Conduct experiments to determine how often mergeSort gets called.

d. Implement this technique in conjunction with tail recursion removal in Exercise I.

e. Explain why the technique in Exercise II would no longer be needed.

Exercise II: Continuing from Exercise I, after part (a),

a. Perform a test so that the smaller subarray is processed by the first recursive call and the larger subarray is processed by the second recursive call.

b. Remove the tail recursion by writing a while loop and altering low or high, as necessary.

c. Prove that the number of recursive calls is logarithmic in the worst case.

Exercise I: The quicksort in the text uses two recursive calls. Remove one of the calls as follows.

a. Rewrite the code so that the second recursive call is unconditionally the last line in quicksort. Do so by reversing the if/else, and returning after the call to insertionSort.

b. Remove the tail recursion by writing a while loop and altering low.