3. (15 points) Let A be an array of n numbers. Suppose that you have an algorithm Algo() that finds the median of any array of numbers! in time linear in the number of elements of the array (that is, in OC#elements in the array)). Show how, using Algo(), Quick Sort can be modified so that it runs in O(n lg n) time in the worst case. Write a pseudocode for the modified Quick Sort, and analyze its running time by describing its recurrence relation and solving it. You can use the subroutine Algo(), which takes as input an array and re- turns the position of the median element in the array, as a black box in the modified Quick Sort