History log of /seL4-test-master/projects/musllibc/src/stdlib/qsort.c
Revision Date Author Comments
# 1477a3be 29-Apr-2011 Rich Felker <dalias@aerifal.cx>

avoid crashing when nel==0 is passed to qsort


# 22263709 27-Apr-2011 Rich Felker <dalias@aerifal.cx>

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.


# b24bc15f 16-Feb-2011 Rich Felker <dalias@aerifal.cx>

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...


# 0b44a031 11-Feb-2011 Rich Felker <dalias@aerifal.cx>

initial check-in, version 0.5.0