/*********************************************
*   Demonstration program of Merge sorting   * 
*      (about n*log(n) comparisons used).    *
* ------------------------------------------ *
* Reference: "A book on C By Al Kelley and   *
* Ira Pohl, The Benjamin/Cummings Publishing *
* Company, Inc, 1984" [BIBLI 09].            *
*                                            *
*                C++ version by J-P Moreau.  *
*                    (www.jpmoreau.fr)       *
* ------------------------------------------ *
* SAMPLE RUN:                                *
*                                            *
* Initial table A:                           *
* 4 3 1 67 55 8 0 4 -5 37 7 4 2 9 1 -1       *
*                                            *
* Sorted table A:                            *
* -5 -1 0 1 1 2 3 4 4 4 7 8 9 37 55 67       *
*                                            *
*********************************************/
#include <stdio.h>

#define MAXSIZE  1024

//Merge Sorting of a[] of size m and b[] of size n
//into c[] of size m+n
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) //pick up any remainder
	c[k++]=a[i++];
  while(j<n)
	c[k++]=b[j++];
}

//use function Merge() to sort an array key[] of size n
//In this version, n is a power of two
void MergeSort(int *key,int n,int *error) {
  int j,k,m, w[MAXSIZE]; //w is a work space
  for (m=1; m<n; m*=2) ;
  if (n==m && n<=MAXSIZE) //n is a power of two <= MAXSIZE
    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++)    //write w back into key
	    key[j] = w[j];
    }
  else {
	if(n!=m) {
	  printf(" \n\n Error #1: size n of array not a power of 2!\n\n");
	  *error=1;
    }
    if(n>MAXSIZE) {
	  printf(" \n\n Error #2: size of array is two bog!\n\n");
	  *error=2;
    }
  }
} //mergesort()


void main() {
  int error=0,i,n=16;
  static int a[] = {4,3,1,67,55,8,0,4,-5,37,7,4,2,9,1,-1};

  printf("\n\n Initial table A:\n");
  for(i=0; i<n; i++)
	printf(" %d ",a[i]);

  MergeSort(a,n,&error);

  if(error==0) {
    printf("\n\n Sorted table A:\n");
    for(i=0; i<n; i++)
	  printf(" %d ",a[i]);
  }

  printf("\n\n");
}

//end of file merge.cpp