/*
 * mergesort.c 
 * p.223
 *
 */


#include <stdio.h>
#define N_DATA 8

void mergesort(int *a, int n);
void merge(int *a, int m, int *b, int n, int *c);
void print_data(int *a);

int main(void){

	int data[N_DATA] = {11, 17, 3, 19, 13, 7, 2, 5};

	print_data(data);
	mergesort(data, N_DATA);
	print_data(data);

	return 0;
}


void mergesort(int *a, int n){

	int i;
	int a1[N_DATA], a2[N_DATA];
	int s1 = (n+1)/2;
	int s2 = n - s1;

	if ( n > 1 ){
		for (i = 0; i < s1; i++){
			a1[i] = a[i];
		}	
		for (i = s1; i < n; i++){
			a2[i-s1] = a[i];
		}	
		mergesort(a1, s1);
		mergesort(a2, s2);
		merge(a1, s1, a2, s2, a);
	}

}


void merge(int *a, int m, int *b, int n, int *c){
	int i=0, j=0;

	while (i<m || j < n ){ 
		if ( j >= n || ( i < m && a[i] < b[j] )){
			c[i+j] = a[i];
			i++;
		}
		else{
			c[i+j] = b[j];
			j++;
		}	
	}
}


void print_data(int *a){

	int i;

	printf("data = {");
	for (i = 0; i < N_DATA; i++){
		if (i<N_DATA-1){
			printf("%2d,", a[i]);
		}
		else{
			printf("%2d}\n", a[i]);
		}
	}
}