chapter 2

insertion sorting:

 
Insertion sort is an efficient algorithm for sorting a small number of
elements. Insertion sort works the way many people sort a hand of playing cards

INSERTION-SORT(A)
1 for j ← 2 to length[A]
2      do key ← A[j]
3      ▹ Insert A[j] into the sorted sequence A[1  j - 1].
4        i ← j - 1
5         while i > 0 and A[i] > key
6               do A[i + 1] ← A[i]
7                i ← i - 1
8        A[i + 1] ← key