source: pcp/src/mergesort2.c@ fdbf0c

/** \file mergesort2.c
 * MergeSort implementation.
 * Unbeknownst that C already chooses the best algorithim according to the
 * problem at hand, a mergesort algorithm was implemented by naturalmergesort(),
 * which does the sorting, and merge() which joins two sorted pieces in an array
 * together.
 * 
   Project: CP
 \author  Jan Hamaekers
 \date  2000
   
   $Id: mergesort2.c,v 1.10 2006/12/05 18:11:16 foo Exp $

   File: mergesort2.c 
   Usage:
   Insert in your Code
   \verbatim
   #include"mergesort2.h"
   double GetKey(void *Element, int i) { }
   void CopyElement(void *Element, int i, void *Element, int j)
   \endverbatim   
   Use:
    naturalmergesort(a,b,l,r,&GetKey,&CopyElement)
     struct Element* a, *b   b als Puffer Speicher reservieren !!!
     int l,r

*/

#ifdef HAVE_CONFIG_H
#include <config.h>
#endif

#include<stdlib.h>
#include "mergesort2.h"

/** Merge two sorted sequences a[l]-a[m] and a[m+1]-a[r] -> a[l]-a[r].
 * Goes in both sequences through all elements, at every one step comparing the two by GetKey
 * and copying the lower one. Eventually, the rest of the remaining sequence is copied (into
 * the dummyarray). And dummyarray back to original one.
 * \param *a  array containging both sequences that is to be sorted
 * \param l start of first sequence
 * \param m end of first sequence, also one before start of second sequence
 * \param r end of second sequence
 * \param *b dummyarray (used for copying hither and thither, size b = r-l+1)
 * \param (*GetKey)(void *, int i, void *) pointer to function that decides whether a[i] is "bigger" than a[j]
 * \param *Args additional arguments for *GetKey function, passed to it on calling
 * \param (*CopyElement)(void *, int i, void *, int j)  pointer to function, copying element b[j] to a[i]
 */
static void merge(void *a, int l, int m, int r, void *b, double (*GetKey)(void *, int i, void *), void *Args, void (*CopyElement)(void *, int i, void *, int j)) {
  int h,i=l,j=m+1,k=l;    // i,j start at their respective sequences
  while (i <= m && j <= r) { // elements are copied from both parts (a[l..m] and a[m+1..r]) in order into dummyarray b[l..r]
    if (GetKey(a,i,Args) <= GetKey(a,j,Args)) {
      CopyElement(b, k, a, i);
      i++;
    } else {
      CopyElement(b, k, a, j);
      j++;
    }
    k++;
  }
  if (i > m) {  // if in one of the sequences there yet remain some elements, copy them (simple for loop)
    for (h=j; h <=r;h++) CopyElement(b, k+h-j, a, h);
  } else {
    for (h=i; h <=m;h++) CopyElement(b, k+h-i, a, h);
  } // finally copy elements back to a
  for (h=l; h <= r; h++) CopyElement(a, h, b, h);
}

/** Mergesort an array /a a[l,-,r].
 * By a divide-and-conquer strategy an array is sorted: Seek first ordered sequence, mark, seek
 * from thereon second order sequence, mark, merge these, until end and then begin again until
 * sorted. Note, that thus already present ordered partial sequences are looked for and used.
 * \param *a array to be sorted  
 * \param l start of to-be-sorted sequence in /a a
 * \param r end of to-be-sorted sequence in /a a
 * \param *b  dummyarray (size  b = r-l+1)
 * \param (*GetKey)(void *, int i, void *) pointer to function that decides whether a[i] is "bigger" than a[j]
 * \param *Args additional arguments for *GetKey function, passed to it on calling
 * \param (*CopyElement)(void *, int i, void *, int j)  pointer to function, copying element b[j] to a[i]
 * \note Should be replaced by C's own qsort-routine, that's always optimal.
 * \sa merge()
 */
void naturalmergesort(void *a, void *b, int l, int r, double (*GetKey)(void *, int i, void *), void *Args, void (*CopyElement)(void *, int i, void *, int j)) {
/* C_min = O(N)
   C_max = O(N)
  */
  int ll=0, mm=0, rr=0;
  do {
    rr = l-1;
    while (rr < r) {
      ll = rr+1;
      mm = ll;
      while (mm < r && GetKey(a, mm+1, Args) >= GetKey(a, mm, Args)) mm++;  // mm is increased until a lower element is found
      if (mm < r) { // was whole sequence in order already?
        rr = mm+1; // mm
        while (rr<r && GetKey(a, rr+1, Args) >= GetKey(a, rr, Args)) rr++;  // from mm on rr is increased until a lower element is found
                merge(a,ll,mm,rr,b,GetKey,Args,CopyElement); // merge these two ordered sequences: a[ll..mm], a[mm+1..rr]
      } else {  // ... we are finished!
        rr = mm;
      }
    }
  } while (ll != l);
}