Challenge: fair partition function

[Andrei Alexandrescu via Digitalmars-d]

Consider defining a function that partitions a range around a given 
index like this:

size_t pivotPartition(alias less = (a, b) => a < b, Range)
(Range r, size_t pivot);

Returns x, one of the the indexes that r[pivot] would have if r were 
sorted. Also, r[0 .. x] contains stuff no greater than r[x] and r[x + 1 
.. $] contains stuff no less than r[x].

The challenge is to implement such a function with fairness: if several 
elements are equal to r[pivot], return the index closest to r.length / 2.

The function should be efficient, minimize calls to less and swap, etc. 
A variant that is efficient but does not implement fairness is below.


Andrei


size_t pivotPartition(alias less = (a, b) => a < b, Range)
(Range r, size_t pivot)
{
     assert(pivot < r.length || r.length == 0 && pivot == 0);
     if (r.length <= 1) return 0;
     import std.algorithm : swapAt;
     r.swapAt(pivot, 0);
     size_t lo = 1, hi = r.length - 1;
     loop: for (;;)
     {
         for (;; ++lo)
         {
             if (lo > hi) break loop;
             if (less(r[0], r[lo])) break;
         }
         // found the left bound
         assert(lo <= hi);
         for (;; --hi)
         {
             if (lo == hi) break loop;
             if (less(r[hi], r[0])) break;
         }
         // found the right bound, swap & make progress
         r.swapAt(lo++, hi--);
     }
     --lo;
     r.swapAt(lo, 0);
     return lo;
}