home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 October / usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso / misc / volume34 / flogger / part01 / merge_sort.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-12-18  |  8.1 KB  |  397 lines
  1.  
  2. /* 
  3.  
  4. NAME
  5.   merge sort
  6.  
  7. DESCRIPTION
  8.  
  9.   Divide up the array into halves, then quarters, then eighths and so
  10.   on until it can be divided no more.  Perform a "tape merge" on
  11.   adjacent sections, building up larger ordered subsections until
  12.   you're done.
  13.  
  14.   This version has some nifty features:
  15.  
  16.   1. It avoids mempcy for arrays of 4 byte or 8 bytes, so sorting
  17.      pointers, ints, longs, float, doubles, or appropriately size tiny
  18.      structures works quickly.  Someday I will add merge2 and merge16
  19.      and round out the collection, but beyond that the savings are
  20.      questionable.
  21.  
  22.   2. After the merges of subsections become larger than a certain
  23.      number of records, a quick check is made to see if the last item
  24.      of the first subsection is less than the first item of the second
  25.      subsection; in this case the array is already in order there so
  26.      there's no point in doing a merge of the two subsections.  This
  27.      feature can be turned off by setting _maybe_sorted to 0.
  28.  
  29.   3. Array indexes and pointer math have been simplified to a degree.
  30.      A sophisticated compiler would have no trouble performing strength
  31.      reduction, but this way some improvement is available even if you
  32.      don't cc -O.
  33.  
  34.   4. If it can't malloc the space it needs, it gives up and calls qsort().
  35.  
  36. AUTHORSHIP
  37.  
  38.   Knuth mentions Von Neumann as the first person who implemented a
  39.   decent merge sort.  Merge sort as an algorithm probably predates 
  40.   electronic computers.
  41.  
  42. REFERENCES
  43.  
  44.   John Von Neumann, Collected Works 5, 1963
  45.   Knuth, Art of Computer Programming Vol 3, pg 159-168
  46.  
  47. COMPLEXITY
  48.  
  49.   O(n log n)
  50.  
  51.   This code is recursive, although the algorithm can be (and often is)
  52.   implemented without recursion.
  53.  
  54.   Unlike many sort algorithms, this takes 2n memory.
  55.  
  56. PORTABILITY PROBLEMS
  57.  
  58.   My choice of sizes for special sort functions and for the
  59.   MAYBE_THRESHOLD aren't necessarily ideal for all computers
  60.   for all time.  
  61.   
  62.   The alignment check is hopelessly RISC-centric, but easy to remove.
  63.  
  64. COPYRIGHT
  65.  
  66.   Copyright 1992 Michael Lee.
  67.  
  68.   (1) Permission to use, copy, distribute, and make changes is granted
  69.   providing that (a) that you do so without charging anyone a fee and
  70.   (b) this copyright notice must be included verbatim in all copies and 
  71.   distributions.  
  72.  
  73.   (2) There is no warranty for this program, to the extent permitted by
  74.   applicable law.  This program is provided "AS IS" without warranty of
  75.   any kind, either expressed or implied, including, but not limited to,
  76.   the implied warranties of merchantability and fitness for a particular 
  77.   purpose.  The entire risk as to the quality and performance of this 
  78.   program is with the user.  Should this program prove defective, the 
  79.   user assumes the cost of all necessary servicing, repair or correction.
  80.  
  81.   (3) In no event unless required by applicable law will the copyright
  82.   holder be liable to the user for damages, including any general,
  83.   special, incidental or consequential damages arising out of the use
  84.   or inability to use this program (including but not limited to loss of
  85.   data or data being rendered inaccurate or losses sustained by the
  86.   user or third parties or a failure of this program to operate with any
  87.   other programs), even if such holder or third party has been advised
  88.   of the possibility of such damages.
  89.  
  90.   (4) Object code produced by a compiler from this code may be 
  91.   incorporated into commercial products without being subject to 
  92.   restrictions (1)(a) or (1)(b).
  93.  
  94. */
  95.  
  96. #include <stdio.h>
  97. #include <malloc.h>
  98. #include <memory.h>
  99. #include <string.h>
  100.  
  101. #include "sorting.h"
  102.  
  103. #ifdef PARANOID
  104. #include <assert.h>
  105. #endif
  106.  
  107. int _maybe_sorted = 1;
  108.  
  109. static int merge4();
  110. static int merge8();
  111. static int mergen();
  112.  
  113. int merge_sort(base, nelem, width, cmpr_func)
  114.   char * base;
  115.   int nelem;
  116.   int width;
  117.   int (*cmpr_func)();
  118. {
  119.   if (width == sizeof(chunk4) && (int) base % sizeof(chunk4) == 0)
  120.     return merge4((chunk4 *) base, nelem, cmpr_func);
  121.   else if (width == sizeof(chunk8) && (int) base % sizeof(chunk8) == 0) 
  122.     return merge8((chunk8 *) base, nelem, cmpr_func);
  123.   else 
  124.     return mergen(base, nelem, width, cmpr_func);
  125. }
  126.  
  127.  
  128. static int merge4(base, nelem, cmpr_func)
  129.   chunk4 * base;
  130.   int nelem;
  131.   int (*cmpr_func)();
  132. {
  133.   int split;
  134.   int a, b;
  135.   chunk4 * c;
  136.   int in_order;
  137.   static chunk4 * out = NULL;
  138.   int mine = 0;
  139.  
  140.   if (out == NULL)
  141.   {
  142.     out = (chunk4 *) malloc(nelem * sizeof(chunk4));
  143.     if (out == NULL)
  144.     {
  145.       qsort((char *) base, nelem, sizeof(chunk4), cmpr_func);
  146.       return 0;
  147.     }
  148.     mine = 1;
  149.   }
  150.  
  151.   split = (nelem+1) / 2;
  152.  
  153.   if (split > 1) 
  154.     (void) merge4(base, split, cmpr_func);
  155.   if (nelem - split > 1) 
  156.     (void) merge4(base+split, nelem-split, cmpr_func);
  157.  
  158.   if (_maybe_sorted && nelem > MAYBE_THRESHOLD &&
  159.       (*cmpr_func)(base+split, base+split-1) >= 0) 
  160.   {
  161.     if (mine)
  162.     {
  163.       free((char *) out);
  164.       out = NULL;
  165.     }
  166.     return 0;
  167.   }
  168.  
  169.   a = 0; 
  170.   b = split;
  171.  
  172.   c = out;
  173.  
  174.   while(a < split)
  175.   {
  176.     if (b >= nelem)
  177.       in_order = 1;
  178.     else 
  179.       in_order = ((*cmpr_func)(base+a, base+b) <= 0);
  180.     
  181.     if (in_order)
  182.     {
  183.       *c = *(base + a);
  184.       c ++;
  185.       a ++;
  186.     }
  187.     else
  188.     {
  189.       *c = *(base + b);
  190.       c ++;
  191.       b ++;
  192.     }
  193.  
  194. #ifdef PARANOID
  195.     assert(c - out <= nelem);
  196. #endif
  197.  
  198.   }
  199.  
  200. #ifdef PARANOID
  201.   assert(c - out <= nelem);
  202. #endif
  203.  
  204.   for (a = 0; a < c - out; a ++) base[a] = out[a];
  205.  
  206.   if (mine)
  207.   {
  208.     free((char *) out);
  209.     out = NULL;
  210.   }
  211.     
  212.   return 0;
  213. }
  214.  
  215.  
  216.  
  217. static int merge8(base, nelem, cmpr_func)
  218.   chunk8 * base;
  219.   int nelem;
  220.   int (*cmpr_func)();
  221. {
  222.   int split;
  223.   int a, b;
  224.   chunk8 * c;
  225.   int in_order;
  226.   static chunk8 * out = NULL;
  227.   int mine = 0;
  228.  
  229.   if (out == NULL)
  230.   {
  231.     out = (chunk8 *) malloc(nelem * sizeof(chunk8));
  232.     if (out == NULL)
  233.     {
  234.       qsort((char *) base, nelem, sizeof(chunk8), cmpr_func);
  235.       return 0;
  236.     }
  237.     mine = 1;
  238.   }
  239.  
  240.   split = (nelem+1) / 2;
  241.  
  242.   if (split > 1) 
  243.     (void) merge8(base, split, cmpr_func);
  244.   if (nelem - split > 1) 
  245.     (void) merge8(base+split, nelem-split, cmpr_func);
  246.  
  247.   if (_maybe_sorted && nelem > MAYBE_THRESHOLD &&
  248.       (*cmpr_func)(base+split, base+split-1) >= 0) 
  249.   {
  250.     if (mine) 
  251.     {
  252.       free((char *) out);
  253.       out = NULL;
  254.     }
  255.     return 0;
  256.   }
  257.  
  258.   a = 0; 
  259.   b = split;
  260.  
  261.   c = out;
  262.  
  263.   while(a < split)
  264.   {
  265.     if (b >= nelem)
  266.       in_order = 1;
  267.     else 
  268.       in_order = ((*cmpr_func)(base+a, base+b) <= 0);
  269.     
  270.     if (in_order)
  271.     {
  272.       *c = *(base + a);
  273.       c ++;
  274.       a ++;
  275.     }
  276.     else
  277.     {
  278.       *c = *(base + b);
  279.       c ++;
  280.       b ++;
  281.     }
  282.  
  283. #ifdef PARANOID
  284.     assert(c - out <= nelem);
  285. #endif
  286.  
  287.   }
  288.  
  289. #ifdef PARANOID
  290.   assert(c - out <= nelem);
  291. #endif
  292.  
  293.   for (a = 0; a < c - out; a ++) base[a] = out[a];
  294.     
  295.   if (mine)
  296.   {
  297.     free((char *) out);
  298.     out = NULL;
  299.   }
  300.  
  301.   return 0;
  302. }
  303.  
  304.  
  305. static int mergen(base, nelem, width, cmpr_func)
  306.   char * base;
  307.   int nelem;
  308.   int (*cmpr_func)();
  309.   int width;
  310. {
  311.   int split, nw, sw;
  312.   int a, b;
  313.   char * c;
  314.   int in_order;
  315.   static char * out = NULL;
  316.   int mine = 0;
  317.  
  318.   nw = nelem*width;
  319.  
  320.   if (out == NULL)
  321.   {
  322.     out = (char *) malloc(nw);
  323.     if (out == NULL)
  324.     {
  325.       qsort(base, nelem, width, cmpr_func);
  326.       return 0;
  327.     }
  328.     mine = 1;
  329.   }
  330.  
  331.   split = (nelem+1) / 2;
  332.   sw = split*width;
  333.  
  334.   if (split > 1) 
  335.     (void) mergen(base, split, width, cmpr_func);
  336.   if (nelem - split > 1) 
  337.     (void) mergen(base+sw, nelem-split, width, cmpr_func);
  338.  
  339.   if (_maybe_sorted && nelem > MAYBE_THRESHOLD &&
  340.       (*cmpr_func)(base+sw, base+sw-width) >= 0) 
  341.   {
  342.     if (mine) 
  343.     {
  344.       free(out);
  345.       out = NULL;
  346.     }
  347.     return 0;
  348.   }
  349.  
  350.   a = 0; 
  351.   b = sw;
  352.   c = out;
  353.  
  354.   while(a < sw)
  355.   {
  356.     if (b >= nw)
  357.       in_order = 1;
  358.     else 
  359.       in_order = ((*cmpr_func)(base+a, base+b) <= 0);
  360.     
  361.     /* todo: try coalescing adjacent iterations into the
  362.        same call to memcpy when in_order is the same */
  363.  
  364.     if (in_order)
  365.     {
  366.       memcpy(c, base+a, width);
  367.       c += width;
  368.       a += width;
  369.     }
  370.     else
  371.     {
  372.       memcpy(c, base+b, width);
  373.       c += width;
  374.       b += width;
  375.     }
  376.  
  377. #ifdef PARANOID
  378.     assert(c - out <= nelem * width);
  379. #endif
  380.  
  381.   }
  382.  
  383. #ifdef PARANOID
  384.   assert(c - out <= nelem * width); 
  385. #endif
  386.  
  387.   memcpy(base, out, c - out);
  388.  
  389.   if (mine)
  390.   {
  391.     free(out);
  392.     out = NULL;
  393.   }
  394.  
  395.   return 0;
  396. }
  397.