/*
   Project: CP
   Jan Hamaekers
   2000

   File: Mergesort 
   Usage:
   Insert in your Code
   #include"mergesort.h"
   double GetKey(void *Element) { } ...
   

   Use:
    naturalmergesort(a,l,r,&GetKey)
     struct Element** a
     int l,r

   See also: GetCrd.c
*/

#include<stdlib.h>

void merge(void **a, int l, int m, int r, void **b, double (*GetKey)(void *)) {
  /* merge two sorted sequnces 
   a[l]...a[m] and a[m+1]...a[r] -> a[l]...a[r]
  b dummyarray (size b = r-l+1)*/
  int h,i=l,j=m+1,k=l;
  while (i <= m && j <= r) {
    if (GetKey(a[i]) <= GetKey(a[j])) {
      b[k]=a[i];
      i++;
    } else {
      b[k] = a[j];
      j++;
    }
    k++;
  }
  if (i > m) {
    for (h=j; h <=r;h++) b[k+h-j] = a[h];
  } else {
    for (h=i; h <=m;h++) b[k+h-i] = a[h];
  }
  for (h=l; h <= r; h++) a[h] = b[h];
}

void naturalmergesort(void **a, int l, int r, double (*GetKey)(void *)) {
  /* sort a[l]...a[r] 
   !!! Nutzt vorhandenen Teilfolgen aus !!!
   C_min = O(N)
   C_max = O(N)
  */
  int ll=0, mm=0, rr=0;
  void **b = (void **) malloc(sizeof(void *)*(r-l+1));
  do {
    rr = l-1;
    while (rr < r) {
      ll = rr+1;
      mm = ll;
      while (mm < r && GetKey(a[mm+1]) >= GetKey(a[mm])) mm++;
      if (mm < r) {
	rr = mm+1;
	while (rr<r && GetKey(a[rr+1]) >= GetKey(a[rr])) rr++;
	merge(a,ll,mm,rr,b,GetKey);
      } else {
	rr = mm;
      }
    }
  } while (ll != l);
  free(b);
}