Practice in insertion sort

After some drilling and practice (33 times so far) of the basic insertion sort on pseudocode, c, perl and python.  I start to feel mildly comfortable with the algorithm.  This kind of exercises are very useful.  In fact, looking back, a deep understanding of one single algorithm, even if it is very simple, seems to sharpen my mind more than browsing thousands of algorithms.  It tends to expose holes in your mind.

It is some progress, I will follow my own goal on each algorithm.   To grok the algorithm : That is to think through it, to write the correct program without the need of compiler/interpreter, to understand it fully theoretically and to know all known extensions of it.

Of course, at the end of the day, if I can propose a better one, I will be ultimately satisfied.

For insertion sort, I am still far far away.  The next thing I plan to do are
1, Learn the basic variations of insertion sort.
2, Do the same practice on selection sort.
3, Do the same practice of linear search.

1 is trivial.  In C, there are around 3 possible code variations floating around on the web just for straight insertion sort. Each of them has their merit.  One important variation is the sentinel version.  It is known to be faster. (Why?)

It's also important to understand the some more advanced version of insertion sort, such as binary insertion sort, shell sort and the new kid, library sort.  Those..... by themselves should be treated with respect and need to be practiced separately.  More on those later. But part of the reason I will do 3 is because it will be the bridge of doing binary search.   It will be two foundations before I start to do a binary insertion sort.

33_P