Insertion Sort

Input: A[1..N], length[A]

for (j=2; j <= length[A]; j++)
{
key = A[j];
i = j-1;
while (A[i] > key && i > 0)
{
A[i+1] = A[i];
i--;
}
A[i+1] = key;
}

Features:
1. sort in place;
2. loop invariant;
3. stable sort;