mirror/musl - mirror of git://git.musl-libc.org/musl

	Commit message (Collapse)	Author	Age	Files	Lines
*	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	Rich Felker	2011-04-27	1	-32/+193
\| \| \| \| \| \| \| \| \| \| \| \| \| \|	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.
*	don't compare elements with themselves during qsort.	Rich Felker	2011-02-17	1	-1/+1
\| \| \| \| \|	this is actually a workaround for a bug in gcc, whereby it asserts inequality of the keys being compared...
*	initial check-in, version 0.5.0 v0.5.0	Rich Felker	2011-02-12	1	-0/+50