Insertion Sort

In this method the elements are inserted at their appropriate place. Hence is the name insertion sort. Let us understand this method with the help of algorithm.

Algorithm Insertion_sort(A[0...n-1])

                            //Problem Description: This algorithm is for sorting the elements using insertion                                      sort

                            //Input: An array of n elements

                            //Output: Sorted array A[0...n-1] in acsending order

                           for i<-1 to n-1 do

                           {

                                  temp<-A[i] //mark A[i]th element

                                  j<-i-1 //set j at previous element of A[i]

                                  while(j>=0)AND (A[j]>temp)do

                                  {

                                   //comparing all the previous elements of A[i] with 

                                   //A[i]. If any greater element is found then insert it at proper position

                                     A[j+1]<-A[j]

                                     j<-j-1

                                   }

                                 A[j+1]<-temp //copy A[i] element at A[j+1]

                              }