It is a very simple method to sort the number in an increasing or decreasing order.

It has various advantages:

1. It is simple to implement.
2. It is efficient on small datasets.
3. It is stable (does not change the relative order of elements with equal keys)
4. It is in-place (only requires a constant amount O (1) of extra memory space).
5. It is an online algorithm, in that it can sort a list as it receives it.

ALGORITHM: INSERTION SORT (A)
1. For k ← 2  to length [A]
2. Do key ← A[k]
3. i=k-1
4. while i>0 and A[i]>key
5. do A[i+1] ← A[i]
6. i=i-1
7. A[i+1] ← key

Analysis:

1. Input: n elements are given.
2. Output: the number of comparisons required to make sorting.
3. Logic: If we have n elements in insertion sort, then n-1 passes are required to find a sorted array.

 In pass 1: no comparison is required
 In pass 2:  1 comparison is required
 In pass 3: 2 comparisons are required
............................................................................
...............................................................................
 In pass n: n-1 comparisons are required 
 Total comparisons: T (n) = 1+2+3+...........+ n-1
                          = 

= o (n

2)
    Therefore complexity is of order n2 

Example:

Illustrate the operation of INSERTION SORT on the array A = (4, 15, 7, 18, and 16).

Solution:

A [] =

41571816

For j=2 to 5

1.  J=2, key=A [2]  
2.         Key=15  
3. I=2-1=1, i=1  
4. While i>0 and A [1]>15  
5. A Condition false, so no change  
6. Now=3, key=A [3] =7  
7. I=3-1=2  
8. I=2, key=7  
9. While i>0 and A [2]>key   
10. Condition is true  
11. So A [2+1] ← A [2]  
12.       A [3] ← A [2]  

i.e.

4151816

1. and i=2-1=1, i=1  
2. while i>0 and A [1]>key  
3. A Condition false. So no change  
4. Then A [1+1] ← key  
5.     A [2] ← 7  

That is

47151816

1. For j=4  
2. Key=A [4]  
3. Key = 18, i=3  
4. Now, while 3>0 and A [3]>18  
5. The Condition is false, No change.  
6. Similarly, j=5      
7.       Key=A [5]  
8. So key=16, i=4  
9. Now while 4>0 and A [4]>16  
10. Condition is true  
11.  So A [5] =16 and i=4-1=3  
12. Now while 3>0 and A [3]>16  
13. Condition is false  
14. So A [3+1] =A [4] =16  

And the sorted array is:

47151618