#include <stdio.h>


/* Change this two to suit your data type */
typedef int key_t;
void printV( key_t *v, int from, int to ) {
	int i;
	for (i=from; i <= to; i++) 
		printf( "%d ", v[i] );
}

#define DEBUG

void mergesort( key_t *v, int l, int r ) {
	
	/* Trivial case or empty arrays */
	if (l>= r) 
		return;


	int m;
	
	/* Partition the array */
	m = (l+r)/2;

#ifdef DEBUG
	printf( "mergesort( v, %d, %d ) : Input array: ", l, r );
	printV( v, l, m );
	printf( " |  " );
	printV( v, m+1, r );
	printf( "\n" );
#endif
	/* Sort the halves recursively */
	mergesort( v, l, m );
	mergesort( v, m+1, r );

	/* Temporary space needed to merge the halves */
	key_t tmp[r-l+1];
	
	/* Merge the halves into tmp */
	int i = 0; /* tmp index */
	int j = l; /* Left half index */
	int k = m+1; /* right half index */
	
	for (i=0; i < r-l+1; i++)
		tmp[i] = 99;
	i=0;

	while (j <= m && k <= r ) {
		if (v[j] < v[k] ) 
			tmp[i] = v[j++];
		else  
			tmp[i] = v[k++];
		i++; 
	}
	while (j <= m) 
		tmp[i++] = v[j++];
	while (k <= r) 
		tmp[i++] = v[k++];


#ifdef DEBUG
	printf( "mergesort( v, %d, %d ) : Output array: ", l, r );
	printV( tmp, 0, r -l );
	printf( "\n" );
#endif


	/* Now copy back tmp to v */
	for (i=0; i <= r-l; i++) 
		v[l+i] = tmp[i];
	

}

int main( void ) {
	key_t v[] = {-4,3,6,1,3,6,2,8};
	mergesort( v, 0, 7 );

	int i;
	for (i=0; i < 8; i++)
		printf( "%d ", v[i] );
	printf( "\n" );
	return 0;
}