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


#include <stdio.h>
#include <stdlib.h>
#define N_DATA 10000
#define LARGEST_NUMBER 1000000


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

int main(void){ 
		
	int i;
	long data[N_DATA]; 
	
	srand48(20080622); 
	
	for (i = 0; i < N_DATA-1; i++){
		data[i] = lrand48() % LARGEST_NUMBER ; 
	}

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

	return 0;
}


void mergesort(long *a, int n){

	int i;
	long 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(long *a, int m, long *b, int n, long *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(long *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]);
		}
	}
}