It is nice to see benchmarks of elementary algorithms, but none of these is new. Benchmarking would be more convincing if more distributions were used. For example, we know that interpolated search is O(lglgn) for uniform distributions that are used here, but can be linear in pathological cases.