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.

(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.

Program Language can be Java.