One against binary searches

[Xinok]

On Monday, 30 July 2012 at 15:40:32 UTC, bearophile wrote:
> This author writes very detailed analyses of low-level 
> computational matters, that appear on Reddit. This blog post he 
> suggests to introduce "offseted binary" or "quaternary search" 
> instead of binary search in Phobos:
>
> http://www.pvk.ca/Blog/2012/07/30/binary-search-is-a-pathological-case-for-caches/
>
> Bye,
> bearophile

My stable sort makes heavy use of binary searches [1], so just 
for fun, I tried inserting a ternary search before the binary 
search. After some optimizing, I found it ideal to use ternary 
search on ranges larger than 8KiB (with 32KiB L1D cache) and 
binary search on anything less. While sorting using additional 
space saw no improvement, in-place sorting went from 408ms to 
371ms. As well, there's a very negligible increase in the number 
of comparisons.


[1] https://github.com/Xinok/XSort/blob/master/stablesort.d#L331