#include 

void merge(int a[], int fi, int fl, int si, int sl, int c[], int ci) {
 fl = fi + fl;
 sl = si + sl;
 while(fi < fl && si < sl) {
  if(a[fi] < a[si])
   c[ci++] = a[fi++];
  else
   c[ci++] = a[si++];
 }
 while(fi < fl)
  c[ci++] = a[fi++];
  while(si < sl)
   c[ci++] = a[si++];
}

void mergePass(int a[], int l, int n, int b[]) {
 int i, fi;
 int q = n/(2*l);
 int s = q*2*l;
 int r = n-s;
 for(i=0;i < q;i++) {
  fi = i*2*l;
  merge(a, fi, l, fi+l, l, b, fi);
 }
 if(r<=l) {
  for(i=s;i < n;i++)
  b[i] = a[i];
 } else
  merge(a, s, l, s+l, r-l, b, s);
}

void mergeSort(int a[], int n) {
 int b[100];
 int l = 1;
 while(l < n) {
  mergePass(a, l, n, b);
  mergePass(b, 2*l, n, a);
  l = l*4;
 }
}

void printArray(int a[], int sa){
 int i;

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


int main() {
 int a[14] = {15,78,58,65,35,26,65,18,59,65,45,75,65,85};
 int n = 14;
 mergeSort(a,n);
 printArray(a,n);
 return 0;
}