home *** CD-ROM | disk | FTP | other *** search
/ The CDPD Public Domain Collection for CDTV 4 / CDPD_IV.bin / networking / uucp / amigauucpsrc / lib / qsort.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-06-29  |  1.6 KB  |  79 lines

  1.  
  2. /*
  3.  *  QSORT.C
  4.  *
  5.  *  Well, I actually implement a merge sort here, because I have no idea
  6.  *  how much stack is available for a quick sort.
  7.  */
  8.  
  9. #include <stdlib.h>
  10. #include <string.h>
  11.  
  12. void
  13. qsort(base, elms, elmSize, cmpfunc)
  14. void *base;
  15. long elms;
  16. long elmSize;
  17. int (*cmpfunc)(const void *, const void *);
  18. {
  19.     long i, j, i1, i2;
  20.     void *tmp = malloc(elmSize);
  21.  
  22.     if (tmp == NULL)
  23.     return;
  24.  
  25.     for (i = 2; (i >> 1) < elms; i *= 2) {         /*  merge sets of 2,4,8.. */
  26.     for (j = 0; j < elms; j += i) {
  27.         long i1 = i >> 1;
  28.         long i2 = i1;
  29.         char *p1;
  30.         char *p2;
  31.  
  32.         if (elmSize == 4) {
  33.         p1 = (char *)base + j * 4;
  34.         p2 = p1 + i1 * 4;
  35.         } else {
  36.         p1 = (char *)base + j * elmSize;
  37.         p2 = p1 + i1 * elmSize;
  38.         }
  39.  
  40.         if (j + i1 + i2 > elms)
  41.         i2 = elms - i1 - j;
  42.  
  43.         /*
  44.          *    Merge p2/i2 into p1/i1 until p2/i2 is exausted.  Note that
  45.          *    i2 might start out negative (in which case i1 is invalid,
  46.          *    but the segment is already sorted anyway)
  47.          */
  48.  
  49.         while (i2 > 0 && i1 > 0) {
  50.         /*
  51.          *  compare current p1/i1 with next p2/i2.  Skip p1 while
  52.          *  p1 < p2.  Otherwise, merge the p2/i2 element into
  53.          *  p1/i1.
  54.          */
  55.  
  56.         if ((*cmpfunc)(p1, p2) <= 0) {
  57.             --i1;
  58.             p1 += elmSize;
  59.         } else {
  60.             if (elmSize == 4) {
  61.             *(long *)tmp = *(long *)p2;
  62.             movmem(p1, p1 + 4, i1 * 4);
  63.             *(long *)p1 = *(long *)tmp;
  64.             } else {
  65.             movmem(p2, tmp, elmSize);
  66.             movmem(p1, p1 + elmSize, i1 * elmSize);
  67.             movmem(tmp, p1, elmSize);
  68.             }
  69.             --i2;
  70.             p2 += elmSize;
  71.             p1 += elmSize;    /*  shifted p1, i1 stays    */
  72.         }
  73.         }
  74.     }
  75.     }
  76.     free(tmp);
  77. }
  78.  
  79.