[OT] Lower and upper median of 4

[Andrei Alexandrescu via Digitalmars-d]

I'm submitting the median paper to 
http://2017.programmingconference.org/track/programming-2017-papers. (It 
was rejected by ALENEX... the short story is there was no open-source 
implementation and they simply didn't buy the results.)

Now I have a C++ implementation available. I wanted to ask for your help 
with lower/upper median of 4, which I coded like this (based on the 
median of 5 posted here by user "tn" aka Teppo Niinimäki):

template <bool leanRight, class T>
void medianOf(T* r, size_t a, size_t b, size_t c, size_t d)
{
     assert(a != b && a != c && a != d && b != c && b != d
         && c != d);
     if (leanRight)
     {
         // In the median of 5 algorithm, consider r[e] infinite
         if (r[c] < r[a]) {
             std::swap(r[a], r[c]);
         }
         if (r[d] < r[b]) {
             std::swap(r[b], r[d]);
         }
         if (r[d] < r[c]) {
             std::swap(r[c], r[d]);
             std::swap(r[a], r[b]);
         }
         if (r[c] < r[b]) {
             std::swap(r[b], r[c]);
         }
         assert(r[a] <= r[c] && r[b] <= r[c] && r[c] <= r[d]);
     }
     else
     {
         // In the median of 5 algorithm consider r[a] infinitely small, 
then
         // change b->a. c->b, d->c, e->d
         if (r[c] < r[a]) {
             std::swap(r[a], r[c]);
         }
         if (r[c] < r[b]) {
             std::swap(r[b], r[c]);
         }
         if (r[d] < r[a]) {
             std::swap(r[a], r[d]);
         }
         if (r[d] < r[b]) {
             std::swap(r[b], r[d]);
         } else {
             if (r[b] < r[a]) {
                 std::swap(r[a], r[b]);
             }
         }
         assert(r[a] <= r[b] && r[b] <= r[c] && r[b] <= r[d]);
     }
}

I started with Teppo's median-of-5 algorithm and eliminated the 
first/last element. Do you think you can do better?


Thanks,

Andrei