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
