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

enum{N=10};

void merge(int *array, int links, int mitte, int rechts) 
{ 
   int i, j, k; 
   int n1 = mitte - links + 1; 
   int n2 =  rechts - mitte; 
 
   int *temp_array, *temp_array2; 
   temp_array = malloc(sizeof(*temp_array) * n1);
   temp_array2 = malloc(sizeof(*temp_array2) * n2);
 	if(temp_array == NULL || temp_array2 == NULL)
 	{
 		printf("Fehler bei der Speicher reservierung!");
   	exit(1);  	
   }
 	
   /* Copy data to temp arrays L[] and R[] */
   for (i = 0; i < n1; i++) 
   {
   	temp_array[i] = array[links + i]; 
   	//printf("temp1 = %d",temp_array[i]);
   }
       
   for (j = 0; j < n2; j++) 
   {
   	temp_array2[j] = array[mitte + 1 + j]; 
   }
       
 
   /* Merge the temp arrays back into arr[l..r]*/
   i = 0; // Initial index of first subarray 
   j = 0; // Initial index of second subarray 
   k = links; // Initial index of merged subarray 
   while (i < n1 && j < n2) 
   { 
       if (temp_array[i] <= temp_array2[j]) 
       { 
           array[k] = temp_array[i]; 
           i++; 
       } 
       else
       { 
           array[k] = temp_array2[j]; 
           j++; 
       } 
       k++; 
   } 
 
   /* Copy the remaining elements of L[], if there 
      are any */
   while (i < n1) 
   { 
       array[k] = temp_array[i]; 
       i++; 
       k++; 
   } 
 
   /* Copy the remaining elements of R[], if there 
      are any */
   while (j < n2) 
   { 
       array[k] = temp_array2[j]; 
       j++; 
       k++; 
   } 
   
   free(temp_array2);free(temp_array);
} 
 
/* l is for left index and r is right index of the 
  sub-array of arr to be sorted */
void mergeSort(int *array, int links, int rechts) 
{ 
   if (links < rechts) 
   { 
       // Same as (l+r)/2, but avoids overflow for 
       // large l and h 
       int mitte = links+(rechts-links)/2; 
 
       // Sort first and second halves 
       mergeSort(array, links, mitte); 
       mergeSort(array, mitte+1, rechts); 
 
       merge(array, links, mitte, rechts); 
   } 
   //printArray(array, n); 
} 
 
/* UTILITY FUNCTIONS */
/* Function to print an array */
void printArray(int *A, int size) 
{ 
   int i; 
   for (i=0; i < size; i++) 
   {
   	printf("%d ", A[i]); 
   }
   printf("\n"); 
} 
 
/* Driver program to test above functions */
int main() 
{ 
 	int i;
 	int *arr = calloc(N,sizeof*arr);
 	srand(time(NULL));
 	
 	for(i = 0; i < N; i++)
 	{
 	    arr[i] = rand() % 100;
    }
 	
   printArray(arr, N); 
 
   mergeSort(arr, 0, N - 1); 

   printArray(arr, N); 
   
   free(arr);
   
   return 0; 
}