MTHRESH qsort qst THRESH

void qsort ( void *  base0, size_t  n, size_t  size, int(__cdecl *compar)(const void *, const void *)    ) Definition at line 179 of file qsort.c. { char *base = (char *)base0; char c, *i, *j, *lo, *hi; char *min, *max; size_t thresh; if (n <= 1) return; if (size == 0) return; compar = compar; thresh = size * THRESH; max = base + n * size; if (n >= THRESH) { qst(size, compar, base, max); hi = base + thresh; } else { hi = max; } /* * First put smallest element, which must be in the first THRESH, in * the first position as a sentinel. This is done just by searching * the first THRESH elements (or the first n if n < THRESH), finding * the min, and swapping it into the first position. */ for (j = lo = base; (lo += size) < hi; ) if (compar(j, lo) > 0) j = lo; if (j != base) { /* swap j into place */ for (i = base, hi = base + size; i < hi; ) { c = *j; *j++ = *i; *i++ = c; } } /* * With our sentinel in place, we now run the following hyper-fast * insertion sort. For each remaining element, min, from [1] to [n-1], * set hi to the index of the element AFTER which this one goes. * Then, do the standard insertion sort shift on a character at a time * basis for each element in the frob. */ for (min = base; (hi = min += size) < max; ) { while (compar(hi -= size, min) > 0) /* void */; if ((hi += size) != min) { for (lo = min + size; --lo >= min; ) { c = *lo; for (i = j = lo; (j -= size) >= hi; i = j) *i = *j; *i = c; } } } }