WDL/mergesort.h

   1 #ifndef _WDL_MERGESORT_H_
   2 #define _WDL_MERGESORT_H_
   3
   4
   5 static void WDL_mergesort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *), char *tmpspace)
   6 {
   7   char *b1,*b2;
   8   size_t n1, n2;
   9
  10   if (nmemb < 2) return;
  11
  12   n1 = nmemb / 2;
  13   b1 = (char *) base;
  14   n2 = nmemb - n1;
  15   b2 = b1 + (n1 * size);
  16
  17   if (nmemb>2)
  18   {
  19     WDL_mergesort(b1, n1, size, compar, tmpspace);
  20     WDL_mergesort(b2, n2, size, compar, tmpspace);
  21   }
  22
  23
  24   do
  25   {
  26     if (compar(b1, b2) > 0) // out of order, go to full merge
  27     {
  28       size_t sofar = b1-(char*)base;
  29       memcpy(tmpspace,base,sofar);
  30       memcpy(tmpspace+sofar, b2, size);
  31       b2 += size;
  32       n2--;
  33
  34       char *writeptr=tmpspace+sofar+size;
  35       while (n1 > 0 && n2 > 0)
  36       {
  37         if (compar(b1, b2) > 0)
  38         {
  39           memcpy(writeptr, b2, size);
  40           b2 += size;
  41           n2--;
  42         }
  43         else
  44         {
  45           memcpy(writeptr, b1, size);
  46           b1 += size;
  47           n1--;
  48         }
  49         writeptr += size;
  50       }
  51
  52       if (n1 > 0) memcpy(writeptr, b1, n1 * size);
  53       memcpy(base, tmpspace, (nmemb - n2) * size);
  54
  55       break;
  56     }
  57
  58     // in order, just advance
  59     b1 += size;
  60     n1--;
  61   }
  62   while (n1 > 0 && n2 > 0);
  63 }
  64
  65 #endif//_WDL_MERGESORT_H_