#include <stdio.h>
#include <stdlib.h>
void insertionSort(int a[],int n);
int main()
{
  int array[8]= { 4,2,7,5,8,1,10,9 },n=8,i;
  insertionSort(array,n);
  printf("Printing Sorted\n" );
  for(i=0;i<n;i++)
  {
    printf("%d\n",array[i]);
  }
  return 0;
}
void insertionSort(int a[],int n)
{
  
  if(n == 1)
    return;
  
  
  insertionSort(a,n-1);
   
  int num = a[n-1] , i;
  for( i= n-2;i>=0;i--)
  {
    if(num < a[i])
    {
      a[i+1] = a[i];
    }
    else
    {
      //a[i] = num;
      break;
    }
  }
  a[i+1] = num;
  //int temp = a[n-1];
  //a[n-1] = a[i+1];
  //a[i+1] = num;
  
  
  
}