Insertion Sort Method


Insertion Sort method is a simple sorting method. It works fine for smaller number of elements in the list.
In order to sort N elements using insertion sort method we required to perform N PASS.
During PASS-1, 1st element of the list is scanned which is trivially sorted.
During PASS-2, 2nd element of the list is scanned and it is compared with 1st element in the list. If 2nd element is smaller then 1st element then they are interchanged.
During PASS-3, 3rd element of the list is scanned and it is compared with 2nd and 1st element respectively.
The same process is repeated until all the elements from the list are scanned and arranged in ascending order.
Thus the order of comparisons is proportional to N2 i.e O(N2)

     

Example of Insertion Sort Method

 
5
2
35
9
3
-2
52
0
Pass1
5
2
35
9
3
-2
52
0
Pass2
2
5
35
9
3
-2
52
0
Pass3
2
5
35
9
3
-2
52
0
Pass4
2
5
9
35
3
-2
52
0
Pass5
2
3
5
9
35
-2
52
0
Pass6
-2
2
3
5
9
35
52
0
Pass7
-2
2
3
5
9
35
52
0
Pass8
-2
0
2
3
5
9
35
52
  Indicates element which is scanned during each Pass.
  Indicates elements within which comparision is performed.


Download Projects


Download Programs