Given an array, a[i], ..., a[j], with j i 2, let k = b(i + j)/2c and choose as the partition element for QUICKSORT the median among a[i], a[j], a[k] (i.e., the value that would be 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 methods in the web. Students should not seek solutions Online, rather students should meet the requirements as listed in this assignment).

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

[50 Points] Use QUICKSORT from the CLRS that uses a normal pivot process and the median-of-three process described above. Test your run time analysis of median-of-three, and then compare the average and worst case run times of QUICKSORT with the pivot processes. Note that you are allowed to use QUICKSORT from the CLRS code provided. Also, remember that CPU time is not a valid measure for testing runtime, instead, use something else such as the number of comparisons, estimated number of steps from code, etc.