#include <stdio.h>

void merge(int * A, const int left, const int mid, const int right)
{
  int B[right -left +1]; // Dieser Schritt ist teuer.
  int i=0, j=left, k=mid+1;

  // wir haben hier zwei Teilarrays in einem Array.
  // j zeigt zunächst auf den Anfang des linken Teils
  // k zeigt auf den Anfang des rechten Teils.
  // In Hilfsarray B wird das jeweilige Minimum der beiden eingesetzt
  // und dann der jeweilige Pointer weitergerückt

  while (j <= mid && k <= right)
  {
    if (A[j] <= A[k])
    {
      B[i++] = A[j++];
    }else{
      B[i++] = A[k++];
    }
  } /* j>mid || k>right */

  while (j <= mid)
    B[i++] = A[j++];

  while (k <= right)
    B[i++] = A[k++];

  for (i=left; i <= right; ++i)
    A[i] = B[i-left];
}

void mymergesort(int * A, const int left, const int right)
{
  if (left < right)
  // Wenn left == right, dann besteht
  // das Teilarray aus nur einer Zelle
  {
    int mid = (left + right) /2;

    // Linke und rechte Hälfte sortieren
    mymergesort(A, left, mid);
    mymergesort(A, mid+1, right);

    // Dann zusammensetzen
    merge(A, left, mid, right);
  }
}

void printarray(const int * A, const int len)
{
  int n;
  for (n=0; n<len; ++n)
  {
    printf("%d ", A[n]);
  }
  printf("\n");
}

int main(void) {
  int A[] = { 5,3,1,2,7,2,4,9,10,20,50,1000,4,33};

  printarray(A, 14);

  mymergesort(A, 0, 13);

  printarray(A, 14);

  return 0;
}