Analysis of the synergy of two algorithms in comparison to their simulation in parallel
In Willard's Searching Unindexed and Nonuniformly Generated Files in $\log \log N$ Time, he references a preliminary version (of the linked paper) entitled "Surprisingly efficient search algorithms for nonuniformly generated files" appearing at the 21st Allerton Conference on Communication Control and Computing in 1983, pp. 656-662. I can't find this paper on the web, but in the later (linked) version above, he says that the older paper shows that the synergy between binary and interpolation search can reduce search time to $o(\log n)$ for certain non-uniform distributions of record keys.

Specifically, call a PDF $\mu$ regular if there are $b_1, b_2, b_3, b_4$ such that $\mu(x) = 0$ for $x &lt; b_1$ or $x &gt; b_2$ and $\mu(x) \geq b_3 &gt; 0$ and $|\mu\prime(x)| &lt; b_4$ for $b_1 \leq x \leq b_2$. For data produced by regular PDFs, interpolation search takes $\Omega(\log n)$ expected time, while binary search takes $\Theta(\log n)$ expected time. Interleaving them, however, takes $O(\sqrt{\log n})$ expected time.

You may also be interested in Willard and Reif's "Parallel processing can be harmful: The unusual behavior of interpolation search", which shows that "parallel processing before the literally last iteration in the search of an unindexed ordered file has nearly no usefulness".