Insertion Sort

Insertion Sort

Insertion Sort

 

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[1] t0 A[i-1]

/* A[ 1 ] to A [i] is sorted. */