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

[deadalnix via Digitalmars-d]

On Monday, 30 November 2015 at 21:50:09 UTC, Andrei Alexandrescu 
wrote:
> On 11/30/15 4:41 PM, H. S. Teoh via Digitalmars-d wrote:
>> What about when element i is matched, swap it with the 
>> (i/2)'th element?
>
> Randomization is essential - without it you have thrashing if 
> you search for 2 elements in alternation. -- Andrei

You'd end up swaping the 2 element in front, but keep them both 
in front, so that sounds like it would have the same behavior as 
the randomized algorithm.

Where it gets hairy, is when you access 2 elements in the array 
that would swap each other without getting in the front (because 
they are at 2n and 2n + 1 with n big).