4 /* A simple heap sort implementation.. only in-place O(nlogn) sort I know. */
6 #define MIN(a, b) ((a)<(b) ? (a) : (b))
8 static void swap(char *a, char *b, size_t len)
13 l = MIN(sizeof tmp, len);
23 static void sift(char *base, size_t root, size_t nel, size_t width, int (*cmp)(const void *, const void *))
27 while (2*root <= nel) {
29 if (max < nel && cmp(base+max*width, base+(max+1)*width) < 0)
31 if (cmp(base+root*width, base+max*width) < 0) {
32 swap(base+root*width, base+max*width, width);
38 void qsort(void *_base, size_t nel, size_t width, int (*cmp)(const void *, const void *))
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);