1. Write the complete algorithm for the merge insert sort sketched out in Section 15.7.
2. Here is a suggestion for what might be a truly optimal sorting algorithm. Pick the best set of comparisons for input lists of size
2. Then pick the best set of comparisons for size 3, size 4, size 5, and so on. Combine them together into one program with a big case statement. Is this an algorithm?
3. Implement the median-finding algorithm of Section 15.6. Then, modify this algorithm to allow finding the ith element for any value i