# Insertion Sort Algorithm

Insertion sort is also very simple sorting algorithm. In this sorting we break the list in two parts.

We pick up a particular value and insert it at the appropriate place in the sorted sub list. That means during the kth iteration the element a[k] is inserted in its proper place in the sorted sub array.

Algorithm

Following are the simple steps to sort array using insert sort:

Pass 1-  a[1] is inserted either before or after a[0] so that a[0] and a[1] are sorted.

Pass 2-  a[2] is inserted either before a[0] or between a[0] and a[1] or after a[1] so that the elements a[0] , a[1] , a[2] are sorted.

Pass k – a[k] is inserted in proper place in the sorted sub array a[0],a[1],a[2]……,a[k-1] so that after insertion , the elements a[0], a[1],a[2],….a[k-1],a[k] are sorted.

Pass n-1 – a[n-1] is inserted in proper place in sorted sub array a[0],a[1],a[2],….a[n-2],so that after insertion, the elements a[0],a[1],a[2],……a[n-1] are sorted

Working of Insertion Sort

To understand the working of insertion sort lets take an unsorted array named a having 7 elements

pass 1: Since a[1] < a[0] , insert element a[1] before a[0] , this give the following table

pass 2: Since a[1] < a[2] , no action is performed.

pass 3: Since a[2] < a[3] , no action is performed.

pass 4: Since a[4] is less than a[0], a[1], a[2] and a[3] , therefor insert a[4] before a[0] , giving the following array.

pass 5: Since a[5] is less than a[1], a[2],a[3] and a[4] , therefor insert a[5] before a[1] and after a[0] , giving the following array.

pass 6: Since a[6] is less than a[2],a[3] and a[4] , therefor insert a[6] before a[2] and after a[1] , giving the following array.

Complexity: