#include <stdio.h>
# include <stdlib.h>
#include <time.h>
#define MAX 99999



/***********************************/
int printarray(int a[], int n)
// Print an array of integers.
{   int i;
  for(i=1; i<= n; i++)
    printf(" %2d ", a[i]);
  printf("\n");
}
/***********************************/
int genintarray(int a[], int asize)
// Generate a random array of integrs with size asize.
{int i;
  srand(100000*time(0));
  for(i=1; i<=asize; i++)
    { a[i]= (97*i*i+rand())% 1000;
    }         
}
/***********************************/

int insertsort(int a[], int n)
{
  int i, j, key;
  for(j=2;j<=n;j++)
    { 
      key=a[j];
      i=j-1;
      while ((i>=1)& (key < a[i]))
	{
	  a[i+1]=a[i];
	  i=i-1;
	}
      a[i+1]=key;
    }
}
/******************************/
int merge(int a[], int p, int q, int r)
{ int i, j, k;
  int tmp[MAX];
  i=p; j=q+1; k=p;
  while ((i<=q) & (j<=r))
    {
      if (a[i] <= a[j]) 
	{ tmp[k]=a[i];
	  i++; k++;
	}
      else 
	{ tmp[k]=a[j];
	  j++; k++;}
    }
  while (i<=q) {tmp[k]=a[i]; k++; i++;}
  while (j<=r) {tmp[k]=a[j]; k++; j++;}
  for (i=p;i<=r;i++) a[i]=tmp[i];
}    
//---------------------------------
int mmergesort(int a[], int p, int r)
{   
  int q;
  if (p > r) { printf("errors\n"); return;}
  if (p < r) {
    q=(p+r)/2;
    mmergesort(a, p, q);
    mmergesort(a, q+1, r);
    merge(a, p, q, r);
  }   
}    

//---------------------------------
int intcompare(const void *a, const void *b)
{
  return *(int *)a- *(int *)b;
}
//---------------------------------

int main()
{ 
  int a[MAX], n;

  printf("type in array size:\n");
  scanf("%d", &n);
  genintarray(a, n);
  printf("Insertion sort:\nInput:\n");
  printarray(a, n);
  insertsort(a, n);
  printf("Output:\n");
  printarray(a, n);
  printf("------------------\n");

  printf("type in array size:\n");
  scanf("%d", &n);
  genintarray(a, n);
  printf("Merge sort:\nInput:\n");
  printarray(a, n);
  mmergesort(a, 1, n);
  printf("Output:\n");
  printarray(a, n); 
  printf("------------------\n");

  printf("type in array size:\n");
  scanf("%d", &n);
  genintarray(a, n);
  printf("Sort with C qsort:\nInput:\n");
  printarray(a, n);
  qsort( &a[1], n, sizeof(a[1]), intcompare);
  printf("Output:\n");
  printarray(a, n);

}