Input : A sequence of n numbers
Output : Sorted output, a permutation (reordering) of input sequence.
A black box algorithm for insertion sort is given below.
INSERTION SORT (A)
/* There is an array of A */
S1: Iterate till the end of the array i = 1 to n
S2 : For each i Insert A[i] into correct position in the region A t0 A[i-1]
/* A[ 1 ] to A [i] is sorted. */