1/*
2 * qsort.c
3 *
4 * This is actually combsort.  It's an O(n log n) algorithm with
5 * simplicity/small code size being its main virtue.
6 */
7
8#include <stddef.h>
9#include <stdlib.h>
10#include <string.h>
11
12static inline size_t newgap(size_t gap)
13{
14    gap = (gap * 10) / 13;
15    if (gap == 9 || gap == 10)
16	gap = 11;
17
18    if (gap < 1)
19	gap = 1;
20    return gap;
21}
22
23void qsort(void *base, size_t nmemb, size_t size,
24	   int (*compar) (const void *, const void *))
25{
26    size_t gap = nmemb;
27    size_t i, j;
28    char *p1, *p2;
29    int swapped;
30
31    if (!nmemb)
32	return;
33
34    do {
35	gap = newgap(gap);
36	swapped = 0;
37
38	for (i = 0, p1 = base; i < nmemb - gap; i++, p1 += size) {
39	    j = i + gap;
40	    if (compar(p1, p2 = (char *)base + j * size) > 0) {
41		memswap(p1, p2, size);
42		swapped = 1;
43	    }
44	}
45    } while (gap > 1 || swapped);
46}
47