/* This program uses the merge algorithm to sort an array, given in the code
   The program contains some concepts in C which were not covered in lectures. 
   I include it here for anyone interested ...

   IT IS NOT PART OF THE COURSE! 

   However, I will provide some more detailed comments about the programming 
   which you can read to help you understand what's going on (hopefully).
*/   

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

void merge( int *, int *, int *, int, int);
void sortmerge( int *, int );

#define KEYSIZE 16

main()
{

 int i, key[] = { 4,3,1,67,55,8,0,4,-5,37,7,4,2,9,1,-1};

 sortmerge(key, KEYSIZE);
 
 printf("after a merge sort the array is \n");
 for (i=0;i<KEYSIZE;i++)
  printf("%d\n", key[i]);

}

void merge(int a[], int b[], int c[], int m, int n)
{
 int i=0,j=0,k=0;
 while (i<m && j<n)
   if( a[i] < b[j] )
     c[k++] = a[i++];
   else
     c[k++] = b[j++];

 while( i<m )
  c[k++] = a[i++];
 while ( j<n )
  c[k++]=b[j++];
}

void sortmerge( int key[], int n)
{
 int j,k,m,*w;

 for (m=1;m<n; m*=2)
   ;

 if ( m!= n){  
   printf( "Error: array size isn't a multiple of 2 .. bye!\n");
   exit(1);
 }

 w = calloc(n, sizeof(int) );
 assert( w != NULL );
 for ( k=1; k<n; k*=2){
   for ( j=0; j<n-k; j+= 2*k)
     merge( key+j, key+j+k, w+j, k,k);
   for( j=0; j<n; ++j)
     key[j] = w[j];
 }

 free(w);
}