This reminds me of an old paper [1] that discuss the performance characteristics of different array layouts for searching in particular. The conclusion is heavily based on the number of cache misses and branch predictor misses that binary search has for different array layouts.
Doesn't have much practical application unfortunately since there is almost zero support for things like eytzinger layout in most standard libraries and sorting an array with a eytzinger layout is a bit harder than a non-decreasing layout.
Doesn't have much practical application unfortunately since there is almost zero support for things like eytzinger layout in most standard libraries and sorting an array with a eytzinger layout is a bit harder than a non-decreasing layout.
[1] "ARRAY LAYOUTS FOR COMPARISON-BASED SEARCHING", Paul-Virak Khuong and Pat Morin, https://arxiv.org/ftp/arxiv/papers/1509/1509.05053.pdf