#include <sys/time.h>

#define NULL 0

/*algoritmo insertion sort que entrega el tiempo [usec] que se 
demora en ordenar el arreglo A de tamaņo n.El tipo devuelto
es long*/
 
long insertion(int A[],int n)
{
int j,i,key;
struct timeval q,r;
gettimeofday(&q,NULL);
for (j=1;j<n;j++)
      { 
      key=A[j];
      i=j-1;
      while(i>=0 && A[i]>key)
      	{A[i+1]=A[i];
	i--;}
       A[i+1]=key;
      }
  gettimeofday(&r,NULL);
  return((r.tv_sec*1000000+r.tv_usec) -(q.tv_sec*1000000+ q.tv_usec));  
  }
  
  /* algoritmo insertion, que llama a funcion copiarreglo en el 75% de la 
ejeucion aproximadamente*/

void insertion_2(int *medio,int A[],int n)
  {
int j,i,key;
for (j=1;j<n;j++)
       {
      if(j==3*n/4) copiarreglo(medio,A,n);  
      key=A[j];
      i=j-1;
      while(i>=0 && A[i]>key)
      	{A[i+1]=A[i];
	i--;}
       A[i+1]=key;
      }
  }