# Insertion Sort

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