diff options
author | Rich Felker <dalias@aerifal.cx> | 2011-04-27 13:27:04 -0400 |
---|---|---|
committer | Rich Felker <dalias@aerifal.cx> | 2011-04-27 13:27:04 -0400 |
commit | 22263709eda9f7d692a0f484fd759f757418dbd7 (patch) | |
tree | 0a801dc54d32eb32e5104377909da1283cdea72c /COPYRIGHT | |
parent | 4bb9b4f3b4a6794da3091f58acbd938ff66fc15b (diff) | |
download | musl-22263709eda9f7d692a0f484fd759f757418dbd7.tar.gz musl-22263709eda9f7d692a0f484fd759f757418dbd7.tar.xz musl-22263709eda9f7d692a0f484fd759f757418dbd7.zip |
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.
Diffstat (limited to 'COPYRIGHT')
-rw-r--r-- | COPYRIGHT | 4 |
1 files changed, 4 insertions, 0 deletions
diff --git a/COPYRIGHT b/COPYRIGHT index 92d8992e..b4b60d10 100644 --- a/COPYRIGHT +++ b/COPYRIGHT @@ -19,6 +19,10 @@ The implementation of DES for crypt (src/misc/crypt.c) is Copyright © 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. |