Insertion Sort

Insertion Sort is a simple sorting algorithm that build final sorted element in the array. The insertion sort give more efficient way and give more advantage than other sort like quick sort, merge sort and heap sort. 

It's specialties are :

• Simple
• More efficient ( Time Complexity O(n²) )
• Only required constant amount of memory requirement. ( O(1) )

Algorithm
------------------------------------------------------------------------------------------------------------
Insertion_Sort(array){
     for i=1 to n-1{
          element = array[i];
          j=i;
          while(j>0 and array[j-1] > element ){
                 array[j] = array[j-1];
                 j=j-1;
          } 
          array[j] = element;
     }
}

Implementation is below :