I learnt insertion sort, I think the most important part of it is:
A[i+1] = A[i]
This is used to move node, e.g. array node. And the stop condition is:
i<0 || a[i] <= key
There’s an important concept: loop invariant. We can use loop invariant to help us understand why an algorithm is right.
In insertion sort, the invariant is every A[1…j] is sorted.So,every time you just find a proper position for A[j] and do some moving action