#include<stdio.h>
#include<stdlib.h>

typedef unsigned long long uint64;

uint64 readClockTick()
{ unsigned int h,l;
  __asm__ ( "xor %%eax, %%eax \t \n"
           "cpuid \t \n"
           "rdtsc \t \n"
           "mov %%edx, %0 \t \n"
           "mov %%eax, %1 \t \n"
           :"=m"(h),
           "=m"(l)
           :);
   return ((uint64)h<<32)+l ;
}

main()
{ int *a;
  int i,j,key,n;
  uint64 start,end;

  printf("input the number of inputs\n");
  scanf("%d",&n);

  a = (int *)malloc(n*sizeof(int));

  for(i=1;i<n; i++)
     a[i] = rand();

  for(i=0; i<n ; i++)
    printf("%d ", a[i]);
    printf("\n");

  start = readClockTick();

  for(j=1; j<n; j++)
    { key = a[j];
       i = j-1 ;
       while(i>=0 && a[i]<key)
         { a[i+1]= a[i];
            i = i-1 ;
         }
       a[i+1] = key;
    }
 
  end = readClockTick();

  for(i=0; i<n ; i++)
    printf("%d ", a[i]);
    printf("\n");
  printf("cpu clocks for sorting %d elements = %ld\n", n, end-start);
}