nsz Git - musl/blob - src/stdlib/qsort.c

   1 #include <stdlib.h>
   2 #include <string.h>
   3
   4 /* A simple heap sort implementation.. only in-place O(nlogn) sort I know. */
   5
   6 #define MIN(a, b) ((a)<(b) ? (a) : (b))
   7
   8 static void swap(char *a, char *b, size_t len)
   9 {
  10         char tmp[256];
  11         size_t l;
  12         while (len) {
  13                 l = MIN(sizeof tmp, len);
  14                 memcpy(tmp, a, l);
  15                 memcpy(a, b, l);
  16                 memcpy(b, tmp, l);
  17                 a += l;
  18                 b += l;
  19                 len -= l;
  20         }
  21 }
  22
  23 static void sift(char *base, size_t root, size_t nel, size_t width, int (*cmp)(const void *, const void *))
  24 {
  25         size_t max;
  26
  27         while (2*root <= nel) {
  28                 max = 2*root;
  29                 if (max < nel && cmp(base+max*width, base+(max+1)*width) < 0)
  30                         max++;
  31                 if (cmp(base+root*width, base+max*width) < 0) {
  32                         swap(base+root*width, base+max*width, width);
  33                         root = max;
  34                 } else break;
  35         }
  36 }
  37
  38 void qsort(void *_base, size_t nel, size_t width, int (*cmp)(const void *, const void *))
  39 {
  40         char *base = _base;
  41         size_t i;
  42
  43         if (!nel) return;
  44         for (i=(nel+1)/2; i; i--)
  45                 sift(base, i-1, nel-1, width, cmp);
  46         for (i=nel-1; i; i--) {
  47                 swap(base, base+i*width, width);
  48                 sift(base, 0, i-1, width, cmp);
  49         }
  50 }