Problem
1. What is the advantage of selection sort over all the other methods we studied?
2. What disadvantage of insertion sort does Shell sort overcome?
3. What is the lower bound on the number of key comparisons that any sorting method must make to put n keys into order, if the method uses key comparisons to make its decisions? Give both the average- and worst-case bounds.