Suppose PARTITION function of QUICKSORT algorithm always produces 9 : 1 proportional split (i.e., after partition, one sub-array contains n/10 elements and the other sub-array contains 9n/10 elements). To take advantage of the fact that insertion sort works really well on arrays of small size, suppose we make the following modification in QUICKSORT algorithm. Whenever any sub-array has k or fewer elements, we call INSERTION SORT and return the answer to the top level QUICKSORT call.
(a)Show that this modified algorithm runs in O(nk + n log(n/k)) time. ( Hint: How many times PARTITION function need to be called? How many times INSERTION SORT needs to be called? Note that worst case running time of INSERTION SORT on an array of n elements is O(n^2 ).)
b)How will you choose so that the modified algorithm will have O(n log n) running time? Show your work.
(c)Suppose PARTITION function always produces a split where one of the sub-arrays has exactly one element in it. In this case, what will be running time of the modified algorithm in terms of n and k? Can you choose an appropriate value of k so that the modified algorithm will run in O(n log n) time? Show your work.