4th writing of insertion sort

Preciseness is still a problem.  It turns out I wrote something like. (Assuming non-decreasing order)

Listing 1
1 for j = 2 to N
2     key = A[j]
3     i = j -1
4     while i > 0 and A[i] > key
5         A[i+1] = A[i]
6         A[i] = key
7         i = i -1

There's nothing wrong with this code but this is not strictly insertion sort.  At line 6, key is exchanged when shifting of the array to right. This is not necessary because we can do (as in TCRC)

Listing 2
1 for j = 2 to N
2     key = A[j]
3     i = j -1
4     while i > 0 and A[i] > key
5         A[i+1] = A[i]
6         i = i -1
7    A[i]= key

This reduces an extra operation in the inner loop.

I also rewrite the C and perl version of the insertion sort.   It is a breeze though it is still easy to make mistakes.   This type of exercise is great to be done routinely.

* Got to remind myself to refresh on Python and Java.   I hope that everytime I write an algorithm, I can think through in at least these 4 langauges.

33_P