Insertion Sort

Insertion Sort algorithm is a sort algorithm which is used to sort an array in a particular order.
It is very less efficient with large lists.

Properties:

1. Stable 
2. O(1) ExtraSpace 
3. O(n^2) comparisons & Swap 
4. Adaptive: O(n) time when nearly sorted
5. Very low overhead

Insertion sort is an algorithm of choice when the data is nearly sorted or when the problem size is small. 

Algorithm

Assume in an array a[1...n] of unsorted elements void insertionSort(int a[],int n) for(i=1;i<n;i++) min=a[i];j=i-1; while(j>=0&&a[j]>min) a[j+1]=a[j];j--; a[j+1]=min;

Example 

The following table shows the steps for sorting the sequence {3, 7, 4, 9, 5, 2, 6, 1}. In each step, the key under consideration is underlined. The key that was moved (or left in place because it was biggest yet considered) in the previous step is shown in bold.

3 7 4 9 5 2 6 1

3 7 4 9 5 2 6 1

3 7 4 9 5 2 6 1

3 4 7 9 5 2 6 1

3 4 7 9 5 2 6 1

3 4 5 7 9 2 6 1

2 3 4 5 7 9 6 1

2 3 4 5 6 7 9 1

1 2 3 4 5 6 7 9

References: 1 

Note: To be edited further with a Code for the algorithm