| Age | Commit message (Collapse) | Author | Lines |
|---|
|
|
|
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.
|
|
|
|
0e10000000000000000000000000000000 was setting ERANGE
exponent char e/p was considered part of the match even if not
followed by a valid decimal value
"1e +10" was parsed as "1e+10"
hex digits were misinterpreted as 0..5 instead of 10..15
|
|
sadly the C language does not specify any such implicit conversion, so
this is not a matter of just fixing warnings (as gcc treats it) but
actual errors. i would like to revisit a number of these changes and
possibly revise the types used to reduce the number of casts required.
|
|
this is actually a workaround for a bug in gcc, whereby it asserts
inequality of the keys being compared...
|
|
|
|
|
