Exercise 4.8 Several students asked questions about Exercise 4.8 on the homework. Here is an explanation that I hope will clear up any confusion. Exercise 4.8 is asking about a different implementation of the Insertion Sort strategy. The input is an unsorted list. The algorithm sorts it. The strategy (for both the standard version and the variant in the exercise) is to build successively longer sorted segments by inserting each key E[i] (for i from 1 to n-1) into its proper place among the first i keys (E[0],...,E[i-1]), which have been sorted by the earlier steps. Remember the picture of an intermediate stage: ----------------------------- | sorted |x| | ----------------------------- 0 i n-1 This is an intermediate stage of the algorithm's progress. When it starts, the sorted segment consists of only the first element and i=1. The standard implementation of the Insertion Sort strategy (the one given in class and in the text) inserts x into the sorted segment by going right to left, one key at a time, comparing x and moving the other key to the right if it is bigger. This insertion step ends when the next key is <= x; then x is inserted in the vacant place. The variant in the exercise uses a different method for the insertion. It uses binary search to find out where x belongs in the sorted segment. (Binary search can easily be modified to return the index of the place where x should go; assume we are using a binary search subroutine that does this.) Then all the bigger keys in the sorted segment are moved one place to the right to make room for x, and x is inserted it its proper place. Thus the Insertion Sort variant in the exercise has the following outline: for (i=1; i