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

[Chris Wright via Digitalmars-d]

On Mon, 30 Nov 2015 16:58:16 -0500, Steven Schveighoffer wrote:

> On 11/30/15 4:50 PM, 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
>>
>>
> What about selecting a random element in 0..k/2 instead of 0..k-1?
> 
> -Steve

You can use that to put a hard upper bound of O(log n), and maybe you'll 
want to use that. However, that also means you have greater odds of a 
single rare query making it to the front of the stack.

If you want to prevent that and still get a guarantee of O(log n), you 
could choose a range of floor(sqrt(k))..k/2.