| Commit message (Expand) | Author | Age | Files | Lines |
|---|
| * | add qsort_r and make qsort a wrapper around it•••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
-fomit-frame-pointer, 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.
| Érico Nogueira | 2021-09-23 | 1 | -17/+20 |
| * | qsort: add a short comment about the algorithm | Leah Neukirchen | 2017-08-11 | 1 | -0/+3 |
| * | avoid crashing when nel==0 is passed to qsort | Rich Felker | 2011-04-29 | 1 | -2/+6 |
| * | replace heap sort with smoothsort implementation by Valentin Ochs•••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 almost-sorted
array of 1M elements (20 being the base-2 log of 1M), i.e. it really
does reduce O(n log n) to O(n) in the mostly-sorted 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.
| Rich Felker | 2011-04-27 | 1 | -31/+192 |
| * | don't compare elements with themselves during qsort.•••this is actually a workaround for a bug in gcc, whereby it asserts
inequality of the keys being compared...
| Rich Felker | 2011-02-17 | 1 | -1/+1 |
| * | initial check-in, version 0.5.0 | Rich Felker | 2011-02-12 | 1 | -0/+50 |
