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

deadalnix via Digitalmars-d digitalmars-d at
Mon Nov 30 14:11:05 PST 2015

On Monday, 30 November 2015 at 21:50:09 UTC, Andrei Alexandrescu 
> 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).

More information about the Digitalmars-d mailing list