about summary refs log tree commit diff
path: root/README
diff options
context:
space:
mode:
authorRich Felker <dalias@aerifal.cx>2011-04-27 13:27:04 -0400
committerRich Felker <dalias@aerifal.cx>2011-04-27 13:27:04 -0400
commit22263709eda9f7d692a0f484fd759f757418dbd7 (patch)
tree0a801dc54d32eb32e5104377909da1283cdea72c /README
parent4bb9b4f3b4a6794da3091f58acbd938ff66fc15b (diff)
downloadmusl-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 'README')
0 files changed, 0 insertions, 0 deletions