THE ALGORITHM

INSERTION SORT (A)
   for j <-- 2 to length[A]
        do key<--A[j]
            //Insert A[j] into the sorted sequence A[1 . . . .j-1]
            i <-- j - 1
                while i > 0 and A[i] > key
                    do A[i + 1] <-- A[i]
                        i <-- i -1
                A[i + 1] <-- key