#include <stdio.h>

void merge(int [], int, int);

void mergesort(int array[], int low, int high)
{
 int m;
 if(low<high)
  {
    m=(low+high)/2;
    mergesort(array, low, m);
    mergesort(array, m+1, high);
    merge(array, low, high);
  }
}

void merge(int array[], int low, int high)
{
 int i,j,k=0,m, n=high-low+1;
 int b[high-low+1];

 m=(low+high)/2;
 /*linke Hälte in Array b kopieren*/
 for(i=low; i<=m; i++)
   b[k++] = array[i];
 /*rechte Hälfte in umgekehrter Reihenfolge in Array b kopieren*/
 for(j=high; j>=m+1; j--)
   b[k++] = array[j];

 i=0; j=n-1; k=low;

 /*Nun das Nächstgrößere Element zurückkopieren bis i und j sich überkreuzen*/
 while(i<=j)
    (b[i]<=b[j])?(array[k++]=b[i++]):(array[k++]=b[j--]);
}

int main()
{
 int i;
 int test_array[] = { 4, 5, 3, 8, 1, 8, 2 };
 mergesort(test_array, 0, 6);

 for(i=0; i<=6; i++)
   printf("%d ",test_array[i]);
 printf("\n");

 return 0;
}