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

void print_info (int * array, int size);
void merge_sort (int * array, int left, int right);
void merge (int * array, int left, int middle, int right);

void print_info(int * array, int size)
{
	int i;
	for (i=0; i<size; i++)
		printf ("%d, ", array[i]);
	printf ("\n");
}

/**Sortiere*/
void merge_sort (int * array, int left, int right)
{
	int middle = ( right + left ) /2;
	//printf ("Merge_sort(left: %d, middle: %d, right: %d) ",left,middle,right);
	// print_info (array, right-left);
	if (left < middle)  merge_sort (array, left, middle);
	if (middle < right) merge_sort (array, middle+1, right);
	merge (array, left, middle, right);
}

/**Mische Elemente zusammen
 * Eingabe: Zwei sortierte Folgen
 * left ist das ganz linke element, right ist das letzte element*/
void merge (int * array, int left, int middle, int right)
{
	int size = right-left;
	int * temp = (int *) malloc((size+1) * sizeof (int));
	int l,r,i;

	//printf ("Merge(left: %d, middle, %d, right: %d), array: ",left, middle, right);
	//print_info (array + left, size); 
	for (l=left,r=middle+1,i=0;l<=middle && r<=right; i++)
	{
		if (array[l] > array[r])
		{
			/*Nimm kleineres!*/
			temp[i] = array[r];
			r++;
		} else {
			temp[i] = array[l];
			l++;
		}
	}

	/** restliche Elemente hinten dran kopieren*/
	if (l < middle)
	{
		/**Es gibt noch linke Elemente*/
		memcpy (temp +i, array + l, (middle -l) *sizeof (int));
	} else if (r<right) {
		memcpy (temp +i, array + r, (right  -r) *sizeof (int));
	}

	memcpy (array+left, temp, size * sizeof (int));
	free(temp);
}

int compare (const void *a, const void *b)
{
	if      ((* (int *)a) <  (* (int *)b)) return -1;
	else if ((* (int *)a) >  (* (int *)b)) return 1;
	else return 0;
}

int main ()
{
	int size 		= 1000000;
	int * array = malloc 	( (size + 1) * sizeof (int));
	int i;
	
	srand(time(0));
	for (i=1; i< size; i++)
		/*scanf ("%d", &array [i]);*/
		// array [i] = rand();
		array [i] = i;

	// printf ("Eingabe: "); print_info(array, size);
	//merge_sort (array, 0, size);
	qsort (array, (size+1),sizeof(int), &compare);
	// printf ("Ergebnis: ");print_info(array, size);
}