On Monday, 30 July 2012 at 17:20:54 UTC, bearophile wrote:
Xinok:
My stable sort makes heavy use of binary searches [1], so just
for fun, I tried inserting a ternary search before the binary
search.
I think in the end he suggests to use a "offseted binary" or a
"quaternary search", over both binary and ternary searches (if
the array is not too much small).
An offseted binary search wouldn't work in this case. The "binary
search" is actually comparing elements in two adjacent ranges
which are equidistant from the center, so it's impossible to
align in both ranges.
I also tried a quaternary search, but it was 25-30ms slower than
a ternary search, albeit it was a bit faster than a binary search.
