Insertion Sort

This article is a stub. It might be missing pseudocode, complexity analysis, or a correctness sketch. It might need some other information which is incomplete perhaps.

Insertion sort

Insertion-Sort(A)

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