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).
