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.
