qsort.c

   1 /* based on musl libc's qsort.c */
   2 #include <stdlib.h>
   3 #include <string.h>
   4
   5 #define MIN(a, b)       ((a) < (b) ? (a) : (b))
   6
   7 static void swap(char *a, char *b, int sz)
   8 {
   9         char tmp[256];
  10         while (sz) {
  11                 int l = MIN(sizeof(tmp), sz);
  12                 memcpy(tmp, a, l);
  13                 memcpy(a, b, l);
  14                 memcpy(b, tmp, l);
  15                 a += l;
  16                 b += l;
  17                 sz -= l;
  18         }
  19 }
  20
  21 static void fix(char *a, int root, int n, int sz, int (*cmp)(void *, void *))
  22 {
  23         while (2 * root <= n) {
  24                 int max = 2 * root;
  25                 if (max < n && cmp(a + max * sz, a + (max + 1) * sz) < 0)
  26                         max++;
  27                 if (max && cmp(a + root * sz, a + max * sz) < 0) {
  28                         swap(a + root * sz, a + max * sz, sz);
  29                         root = max;
  30                 } else {
  31                         break;
  32                 }
  33         }
  34 }
  35
  36 void qsort(void *a, int n, int sz, int (*cmp)(void *, void *))
  37 {
  38         int i;
  39
  40         if (!n)
  41                 return;
  42         for (i = (n + 1) >> 1; i; i--)
  43                 fix(a, i - 1, n - 1, sz, cmp);
  44         for (i = n - 1; i; i--) {
  45                 swap(a, a + i * sz, sz);
  46                 fix(a, 0, i - 1, sz, cmp);
  47         }
  48 }