Quick Sort as explained in class uses a Pivot value to arrange all numbers greater than the pivot on one

side and all values smaller than the pivot on the other side. Pivot in the class example used the first

element of the array. Median of three rule uses the median of the first last and the middle elements

of the array as the Pivot so that we avoid the chance of picking the smallest or the largest element in the

array.

a) Write the status of the list F= (12,2,16, 30,8,28,4,10,20,6,18) at the end of each phase of

recursive Quick sort using median of three rule to determine the pivot key.

b) Show that recursive QuickSort takes O(n^2) time when input list is already in sorted order

c) Write a non recursive version of Quicksort incorporating the median of three rule to determine

the pivot key. You can use the F array above from a) for your testing.

d) Show that the non recursive version of Quicksort above takes O( n logn) time on already sorted

list.