I have been working the ideas central to problem 3.5 into a lecture. The version on the website now has
1) A corrected version of picture for insertion sort on 4 items Previous image had mirror symetry that isn't right 2) A picture of binary insertion sort on 4 items 3) An introduction to Merge Insertion, an advanced sorting technique 4) More figures As with many of our problems, there is more here than you need to know. It is enough to write a version that takes ordinary Insertion Sort, or a sort of your choice. However, I'm always reluctant to pass up a teaching moment. You may find more details in the original PDF I sent around, and more ideas in the posted lecture notes. As always, questions are welcome. - jeff parker