Problem: Suppose we pick three random elements from the array, and then use the median of those three numbers as the pivot. If the array has size 2 then we pick either element as the pivot. Execute this variation of quick sort on the array [4; 2; 5; 6; 1; 7; 3; 8] where the three random numbers are always chosen as the first 3 elements in the array.
Q1. What is the best-case runtime of this new Quicksort?
Q2. What is the worst-case runtime of this new Quicksort?
Q3. Do you think that it is less likely that the worst-case scenario occurs?