a. What is a best case for Insertion Sort? Describe how the elements in the list would be arranged, and tell how many comparisons of list elements would be done in that case.

b. In the average analysis of Insertion Sort we assumed that the keys were distinct. Would the average for all possible inputs, including cases with duplicate keys, be higher or lower? Why?