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

#define MAX 999
int a[MAX], b[MAX], n;

int printarray(int a[], int n)
{   int i;
  for(i=1; i<= n; i++)
    printf("%3d ", a[i]);
  printf("\n");
}
/***********************************/
int genintarray(int a[], int asize)
{int i;
  //   srand(time(0));
  for(i=1; i<=asize; i++)
    { a[i]= (97*i*i+rand())% 50;
    }         
}
/***********************************/

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 0;}
  if (p < r) {
    q=(p+r)/2;
    mmergesort(a, p, q);
    mmergesort(a, q+1, r);
    merge(a, p, q, r);
  }   
}
/******************************/ 
int swap( int* a, int* b)
{ int tmp;
  tmp=*a;
  *a= *b;
  *b=tmp;  
}
/******************************/
int partition(int a[], int p, int r)
{ int i; // the upper limit of the first half 
  int x; // value of the pivot
  int j;
  x=a[r];  i=p-1;
  for (j=p; j < r; j++)
    { if (a[j] < x) 
	{ i=i+1;
	  swap(&a[i], &a[j]);
	}}
  swap(&a[i+1], &a[r]);
  return(i+1); 
}
/******************************/
int randpartition(int a[], int p, int r)
{ int i;
  if (p < r) {
    srand(time(0));
    i=p+ (rand()% (r-p+1));
    swap(&a[i], &a[r]);
    return partition(a, p, r);
  }}

/******************************/
int randquicksort(int a[], int p, int r)
{int q;
  if(p < r) {
    q=randpartition(a, p, r);
    randquicksort(a, p, q-1);
    randquicksort(a, q+1, r);
  }
}
/******************************/
int quicksort(int a[], int p, int r)
{int q;
  if(p < r) {
    q=partition(a, p, r);
    quicksort(a, p, q-1);
    quicksort(a, q+1, r);
  }
}
/******************************/
// Find the median element of two sorted arrays.
 
void median2sortedarray(int x[], int xp, int xr, 
			int y[], int yp, int yr)
{int xmid, ymid, nn;
  nn=xr-xp+1;
  if (nn==1) 
    {if  (x[xp]< y[yp])
	printf("Median=%3d in array X[%d].\n", x[xp], xp);
      else printf("Median=%3d in array Y[%d].\n", y[yp], yp);
      return;}   
  xmid=(xp+xr)/2;
  ymid=(yp+yr)/2;
   
  if(x[xmid]== y[ymid])
    { if ((nn%2)==0) printf("Median=%3d in array X[%d] and Y[%d].\n", x[xmid], xmid, ymid); 
      else 
	{ if (x[xmid+1]< y[ymid+1])
	    printf("Median=%3d in array X[%d].\n", x[xmid+1], xmid+1);
	  else if (x[xmid+1]> y[ymid+1])
	    printf("Median=%3d in array Y[%d].\n", y[ymid+1], ymid+1); 
	  else printf("Median=%3d in array X[%d] and Y[%d].\n", x[xmid+1], xmid+1, ymid+1);
	}
      return;     
    }
  else if (x[xmid] < y[ymid])
    { if ((nn%2)==0) median2sortedarray(x, xmid+1, xr, y, yp, ymid);
      else median2sortedarray(x, xmid, xr, y, yp, ymid);}
  else 
    { if ((nn%2)==0)median2sortedarray(x, xp, xmid, y, ymid+1, yr);    
      else median2sortedarray(x, xp, xmid, y, ymid, yr);}
}

/******************************/
int main()
{ 

  printf("Type in array size:\n");
  scanf("%d", &n);
  srand(time(0)); 
  genintarray(a, n);

  insertsort(a, n);
  printf("X:");
  printarray(a, n);
   
  genintarray(b, n);

  mmergesort(b, 1, n);
  printf("Y:");
  printarray(b, n); 
  printf("------------------\n");
  median2sortedarray(a, 1,n, b,1,n);  

}