home *** CD-ROM | disk | FTP | other *** search
/ The C Users' Group Library 1994 August / wc-cdrom-cusersgrouplibrary-1994-08.iso / listings / v_11_07 / mergesrt.c < prev    next >
C/C++ Source or Header  |  1993-02-04  |  4KB  |  118 lines
  1. #include <stddef.h>     /* get #define for NULL */
  2. #include <stdlib.h>
  3.  
  4. #define UNREADY 1
  5. #define READY 2
  6. #define PART struct part
  7.  
  8. PART
  9.    {
  10.    unsigned start, n_elems, state;
  11.    };
  12.  
  13. /* The theology underlying this mergesort routine is to emulate   */
  14. /* the workings of a recursive routine without actually recurring */
  15. /* and getting function call overhead.  The code in MERGESRT.BAK  */
  16. /* does exactly what this code does,  except that it does the     */
  17. /* recursion and is thus slower;  you might want to refer to it   */
  18. /* if you get bogged down here.                                   */
  19. /*    The actual method is as follows:                            */
  20.  
  21. /*    1: Think in terms of parts.  The array to be sorted is one */
  22. /*       big part with start = 0, n_elems = n_elements.  Sorting */
  23. /*       a part requires sorting each half of the part,  then    */
  24. /*       merging each half together.                             */
  25. /*    2: To sort a part:  if it's UNREADY,  i.e.  its halves are */
  26. /*       unsorted,  then mark it as READY and add its two halves */
  27. /*       on as being UNREADY.  If it's READY,  this means that   */
  28. /*       each half has been sorted,  so merge the halves and     */
  29. /*       'forget' about that part,  i.e.,  decrement the number  */
  30. /*       of parts.                                               */
  31. /*    3: Eventually,  you have no parts,  and you're done.       */
  32.  
  33. /*    Originally written 2 Feb 93 by Bill Gray                      */
  34.  
  35. static void msort( char *data, char *temp_data, unsigned n_elements,
  36.       unsigned elem_size, int (*compare)(void *elem1, void *elem2))
  37. {
  38.    char *part1, *part2, *dest;
  39.    unsigned n_parts, start, n_elems;
  40.    PART parts[32], *part_ptr;
  41.  
  42.    n_parts = 1;
  43.    parts[0].start = 0;
  44.    parts[0].n_elems = n_elements;
  45.    parts[0].state = UNREADY;
  46.    while( n_parts)
  47.       {
  48.       part_ptr = parts + (n_parts - 1);
  49.       start = part_ptr->start;
  50.       n_elems = part_ptr->n_elems;
  51.       if( part_ptr->state == UNREADY)
  52.          {
  53.          if( n_elems > 1)
  54.             {
  55.             part_ptr->state = READY;
  56.             part_ptr[1].state = part_ptr[2].state = UNREADY;
  57.             part_ptr[1].start = start;
  58.             part_ptr[1].n_elems = n_elems / 2;
  59.             part_ptr[2].start = start + n_elems / 2;
  60.             part_ptr[2].n_elems = n_elems - n_elems / 2;
  61.             n_parts += 2;
  62.             }
  63.          else
  64.             n_parts--;
  65.          }
  66.       else     /* part_ptr->state == READY;  each half is ready for merging */
  67.          {
  68.          unsigned remains1, n1, remains2, n2;
  69.  
  70.          remains1 = n1 = n_elems / 2;
  71.          remains2 = n2 = n_elems - n1;
  72.          part1 = data + start * elem_size;
  73.          part2 = part1 + n1 * elem_size;
  74.          dest = temp_data;
  75.          while( remains1 && remains2)
  76.             {
  77.             if( compare( part1, part2) < 0)
  78.                {
  79.                memcpy( dest, part1, elem_size);
  80.                part1 += elem_size;
  81.                remains1--;
  82.                }
  83.             else
  84.                {
  85.                memcpy( dest, part2, elem_size);
  86.                part2 += elem_size;
  87.                remains2--;
  88.                }
  89.             dest += elem_size;
  90.             }
  91.                /* if,  as is usual,  one half "runs out" before the other, */
  92.                /* copy the remainder of the other half onto the list. */
  93.          memcpy( dest, part1, remains1 * elem_size);
  94.          dest += remains1 * elem_size;
  95.          memcpy( dest, part2, remains2 * elem_size);
  96.             /* we now have a sorted version... copy it back to */
  97.             /* the original buffer,  and we're done */
  98.          memcpy( data + start * elem_size, temp_data, n_elems * elem_size);
  99.          n_parts--;
  100.          }
  101.       }
  102. }
  103.  
  104. int my_mergesort( void *data, unsigned n_elements, unsigned elem_size,
  105.                      int (*compare)(void *elem1, void *elem2))
  106. {
  107.    void *temp_data;
  108.  
  109.          /* we need a temporary scratch space as big as the input array */
  110.    temp_data = calloc( n_elements, elem_size);
  111.  
  112.    if( temp_data)
  113.       msort( data, temp_data, n_elements, elem_size, compare);
  114.    free( temp_data);
  115.          /* only possible error is that temp_data didn't calloc */
  116.    return( temp_data == NULL);
  117. }
  118.