And here's another interesting algorithm/structure: Randomized Slide to Front

[Ola Fosheim Grøstad via Digitalmars-d]

On Monday, 30 November 2015 at 21:33:31 UTC, Andrei Alexandrescu 
wrote:
> With RStF, worst case search time remains O(n), as is the 
> unsuccessful search. However, frequently searched elements

If you just do a linear search then shifting down the array in 
another pass won't change the complexity. O(2N) == O(N) But you 
could also just shift down the array while searching since if the 
elements are less than the cacheline-size then you already have 
everything in registers/first level cache.

(The write back cost from cache to memory is contextual and 
depends on many factors.)