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.
diff --git a/COPYRIGHT b/COPYRIGHT
index 92d8992..b4b60d1 100644
--- a/COPYRIGHT
+++ b/COPYRIGHT
@@ -19,6 +19,10 @@
1994 David Burren. It is licensed under a BSD license compatible with
the GNU LGPL.
+The smoothsort implementation (src/stdlib/qsort.c) is Copyright © 2011
+Valentin Ochs and is licensed under an MIT-style license compatible
+with the GNU LGPL.
+
The x86_64 port was written by Nicholas J. Kain. See individual files
for their copyright status.