1. Implement an optimized version of quicksort and experiment with combinations of the following:
a. pivot: ?rst element, middle element, random element, median of three, median of ?ve
b. cutoff values from 0 to 20
2. Write a routine that reads in two alphabetized ?les and merges them together, forming a third, alphabetized, ?le.
3. Suppose we implement the median-of-three routine as follows: Find the median of a[left], a[center], a[right], and swap it with a[right]. Proceed with the normal partitioning step starting i at left and j at right-1 (instead of left+1 and right-2).
a. Suppose the input is 2, 3, 4, ... , N - 1, N, 1. For this input, what is the running time of this version of quicksort?
b. Suppose the input is in reverse order. For this input, what is the running time of this version of quicksort?