Given an array, a[i],...,a[j], with j i 2, let k = (i + j)/2 and choose as the partition element for Quicksort the median among a[i], a[j], a[k] (i.e., the value that would be in the middle if a[i], a[j], and a[k] were sorted). This is called median-of-three partitioning. (NOTE: There are several descriptions of the median-of-three method on the web. Students are not permitted to seek out these descriptions in solving this problem.)

(a) [15 points] Write pseudocode for median-of-three partitioning.

(b) [15 points] What is the running time of median-of-three partitioning? Justify your answer.

(c) [20 points] What is the running time of Quicksort if you use median-of-three partitioning on an input set that is already sorted? Justify your answer.

(d) [50 points] Implement Quicksort using a normal pivot process and the median-of-three process described above. Test your run time analysis of medium-of-three, and then compare the average and worst case run times of Quicksort with the two pivot processes. Note that you must implement all of these algorithms from scratch. Also remember that CPU time is not a valid measure for testing run time. You must use something such as the number of comparisons. (In JAVA)