Insertion Sort Method

This method sorts the data by inserting value into its proper poistion.

The steps used in this method are

Step 1: A1 itself is sorted.

Step 2: Compare A2 with A1

• In case of ascending order ,  

  A2 <= A1 if yes then x = A2 ; A2 = A1 ; A1 = x

                             if no 'No Change'

• In case of descending order

    A2 >= A1 if yes then x = A2 ; A2 = A1 ; A1 = x

                             if no 'No Change'

Step 3: Compare A3 with A1 and A2

• In case of ascending order ,  

  A3 <= A1  or A3<= A2  

  then insert A3 in that postion where the condition holds true (first) , 

          otherwise 'No Change'

• In case of descending order

   A3 >= A1  or A3>= A2  

  then insert A3 in that postion where the condition holds true (first) , 

          otherwise 'No Change'

.

.

.

.

Step n : Compare An with A1, A2, A3 ... An-1 

• In case of ascending order ,  

  An <= A1  or An<= A2  or ... An <= An-1 

  then insert An in that postion where the condition holds true (first) , 

          otherwise 'No Change'

• In case of descending order

    An >= A1  or An>= A2  or ... An >= An-1 

  then insert An in that postion where the condition holds true (first) , 

          otherwise 'No Change'

Complexity 

• Worst Case : n(n-1)/2 = o(n²)
• Average Case : n(n-1)/4 = o(n²)

Algorithm

1. For step= 1 to n
    Set temp=a[step]
    Set i=step-1
    while temp=0)
            Set a[i+]=a[i]
    end while
    Set a[i+1]=temp
   End For
2. Print Sorted Data
3. Exit