Insertion Sort

 INCREASING ORDER:

1.       for(j=1;j<size;j++)
2.      {
3.              temp=arr[j];
4.           for(i=j-1;i>=0&&arr[i]>temp;i--)
5.               arr[i+1]=arr[i];
6.              arr[i+1]=temp;
7.       }

Explanation:

   Insertion sort is the way we play cards.already we have some cards(joker,king e.t.c)  which are in increasing order in our hands.

so if you pick up a new card first you check the card arrangement from right to left side and accordingly you shift some cards to right and may place the pick up card in the middle

       1.so while picking up we already have some cards in hands..so

            start from j=1;

      2.To show picking up, store that value in temp variable

      3.now for comparing from right to left take i=j-1 and decrement it                  

             using a for loop until i>=0

     4.understand that this loop is for shifting the elements to right which are greater than temp. so put a condition arr[present card]>temp,so all cards greater than temp will shift right side.This loop get terminated when

that condition is false.It means we have found a card which is atmost less than required card.So place the Temp variable at right of less than card for sorting..so arr[i+1]=temp

Time Complexity:

 

  Best Case:   O(n)

               

                   This is When the input is already sorted Then first loop is executed n-1 times and in second loop because of arr[i]>temp,always the condition fails and loop is not executed so  O(n) .

Average case Worst Case: O(n^2)

           

                    The worst case is when the input is in reverse order so,FIrst loop N-1 times and Second loop N times .Actually more than N and less than N^2..So product of them becomes O(n^2).

   

Space Complexity:

  In this sorting,except array we used only i,j,temp variables so

      O(1).