Project: better partition

[Xinok via Digitalmars-d]

On Wednesday, 18 May 2016 at 19:54:19 UTC, Andrei Alexandrescu 
wrote:
> ...
> No worries. Please take anything you need from there for your 
> code, make it better, and contribute it back to the stdlib! -- 
> Andrei

As it turns out, easier said than done.  I've been thinking about 
it for a few days now but I don't see a simple way to optimally 
merge the two techniques. The way that I alternate between 
iterating "lo" and "hi" (or lef/rig in my code) doesn't really 
work when you need to keep the iterator stationary until 
something fills the vacancy.

This is the best solution I have so far and it doesn't feel like 
a good solution at that:

     for (;;)
     {
         ++lo;
         for (;;)
         {
             if(r[lo] < p)  ++lo; else break;
             if(r[lo] <= p) ++lo; else break;
         }

         if(lo > hi) lo = hi;
         r[hi] = r[lo];

         --hi;
         for (;;)
         {
             if(p < r[hi])  --hi; else break;
             if(p <= r[hi]) --hi; else break;
         }
         if(lo >= hi) break;
         r[lo] = r[hi];
     }

The idea is simple: alternate the check for equality in hopes of 
skipping some equal elements. Unfortunately, this modification 
requires a little more work and TWO sentinels at either end of 
the range because it may skip over the first.

In most real-world data, there's only marginal gains to be made 
in skipping over equal elements, too small to justify 
compromising the gains achieved by using sentinels and vacancies. 
So unless an optimal solution exists, it's just not worth it.