Suppose that the recursive quicksort algorithm receives an integer parameter, depth, from the dirver that is initially approximately 2lgn , where n is the size of the array being sorted.

1). Modify quicksort to call heapsort on its current subarray if the level of recursion has reached depth. Provide pseudocode for this modified algorithm. You can make use of the heap routine from below.

2). Prove that the worst-case running time of this modified algorithnm is O(nlgn).

function Heapsort(arr)

Heapify array arr;

for i = n-1 down to 1 do

swap arr[i] with arr[0];

restore heap property for the tree arr[0],..., arr[i-1] by percolating down the root;

end