Note: when a problem has an array of real numbers, you cannot use counting sort or radix sort. 1 Picking Quicksort pivot Consider the "cheating" version of Quicksort where we keep picking a pivot until we find one that is in the "middle haf" of the array that is one that results in a partition where the smaler side has at least n/4 items. The probability of finding such a pivot is 1/2. Thus the expected number of times we have to pick a pivot until we find an acceptable one is 2. Suppose that we revise our pivot picking strategy as follows: pick 3 numbers from the array uniformly (with replacement), sort the 3 numbers and use the middle of the 3 as the pivot. What is the probability that our chosen pivot ite is i the "middle half" What is the expected number of times that we have to pick a pivot in this manner until we find one that is in the "middle half"? Show your work