/*   USE MERGE TO DO MERGESORT

/*  	Write a C function to merge 2 arrays, assumed to be ordered by ascending values,
	and store the result in a 3rd array, so it in turn is ordered. 
    Follow the function prototype given above the cut line.
	Put your entire function betweenb the cut lines	
*/
#include <stdio.h>       /* for printf in C programs */

#define LEN	15

void merge (int[], const int[], int , const int[], int);
void mergesort(int[], int n);

int main() {
  int a[LEN] = {1,2,3,8,42,89,5,-66,-1,2,4,7,11,123,0};
  int* mp = a;	// point to successive result elements

  mergesort( a, LEN);
  for (int i=0; i<LEN; i++)
     printf ("%d,",*mp++);
  printf("\n");
  return 0;
}
//----------------------------------------------------------------
void mergesort  (int old[], int n)
{   if (n<2) return;	// cannot be out of order
//printf("%d\n",n);
    int mid = n/2;	// half the size (2 parts)

    mergesort (old, mid);	// sort first half
    mergesort (old+mid, n-mid);	// sort second half
    
// merge the two halves
    int* new = malloc(n*sizeof(int));	// allocate enough space
    merge (new, old, mid, old+mid, n-mid);
// copy back to old from new
    int* np = new;
    for (int i=0; i<n; i++)
      *old++ = *np++;
    free(new);		// release new space
}
//----------------------------------------------------------------

void merge (int dest[], const int s[], int size1, const int t[], int size2) {


/*    YOUR CODE TO MERGE 2 ARRAYS HERE */

}
/*--------------  end cut  -----------------------
/*               End of file 	*/