Age  Commit message (Collapse)  Author  Lines 

we make qsort a wrapper by providing a wrapper_cmp function that uses
the extra argument as a function pointer. should be optimized to a tail
call on most architectures, as long as it's built with
fomitframepointer, so the performance impact should be minimal.
to keep the git history clean, for now qsort_r is implemented in qsort.c
and qsort is implemented in qsort_nr.c. qsort.c also received a few
trivial cleanups, including replacing (*cmp)() calls with cmp().
qsort_nr.c contains only wrapper_cmp and qsort as a qsort_r wrapper
itself.






Smoothsort is an adaptive variant of heapsort. This version was
written by Valentin Ochs (apo) specifically for inclusion in musl. I
worked with him to get it working in O(1) memory usage even with giant
array element widths, and to optimize it heavily for size and speed.
It's still roughly 4 times as large as the old heap sort
implementation, but roughly 20 times faster given an almostsorted
array of 1M elements (20 being the base2 log of 1M), i.e. it really
does reduce O(n log n) to O(n) in the mostlysorted case. It's still
somewhat slower than glibc's Introsort for random input, but now
considerably faster than glibc when the input is already sorted, or
mostly sorted.


this is actually a workaround for a bug in gcc, whereby it asserts
inequality of the keys being compared...


