a. Write pseudocode for median of three partitioning b.

What is the running time of median-of-three partitioning? Justify your answer.

Given an array, ali],...,alj], with j-i 2, let k-LG+5)/2 and choose as the partition element for QUICKSORT, the median among a[i], alj], 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 partitionin