How do I calculate the "median of five" in C#?

Question

The median of five is sometimes used as an exercise in algorithm design and is known to be computable using only 6 comparisons.

What is the best way to implement this "median of five using 6 comparisons" in C# ? All of my attempts seem to result in awkward code :( I need nice and readable code while still using only 6 comparisons.

public double medianOfFive(double a, double b, double c, double d, double e){
    //
    // return median
    //
    return c;
}

Note: I think I should provide the "algorithm" here too:

I found myself not able to explain the algorithm clearly as Azereal did in his forum post. So I will reference his post here. From http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1061827085

Well I was posed this problem in one of my assignments and I turned to this forum for help but no help was here. I eventually found out how to do it.

1. Start a mergesort with the first 4 elements and order each pair (2 comparisons)

2. Compare the two lower ones of each pair and eliminate the lowest one from the possibilities (3 comparisons)

3. Add in the 5th number set aside to the number without a pair and compare the two (4 comparisons)

4. Compare the two lowest of the two new pairs and eliminate the lower one (5 comparisons)

5. Compare the one by itself and the lower of the last pair and the lower number is the median

   The possible median is within the parentesis

(54321)

5:4 3:2 2 comparisons

(4<5 2<3 1)

4:2 3 comparisons

2(4<5 3 1)

1:3 4 comparisons

2(4<5 1<3)

4:1 5 comparisons

1,2(4<5 3)

4:3 6 comparisons

1,2(3)4,5

Three is the median

Here is the C++ code I wrote to find median of five. Don't mind its awkwardness:

double StageGenerator::MedianOfFive(double n1, double n2, double n3, double n4, double n5){
    double *a = &n1, *b = &n2, *c = &n3, *d = &n4, *e = &n5;
    double *tmp;

    // makes a < b and b < d
    if(*b < *a){
        tmp = a; a = b; b = tmp;
    }

    if(*d < *c){
        tmp = c; c = d; d = tmp;
    }

    // eleminate the lowest
    if(*c < *a){
        tmp = b; b = d; d = tmp; 
        c = a;
    }

    // gets e in
    a = e;

    // makes a < b and b < d
    if(*b < *a){
        tmp = a; a = b; b = tmp;
    }

    // eliminate another lowest
    // remaing: a,b,d
    if(*a < *c){
        tmp = b; b = d; d = tmp; 
        a = c;
    }

    if(*d < *a)
        return *d;
    else
        return *a;

} 

It should be more compact, isn't it ?

---

As @pablito pointed out in his answer, the built-in List.Sort() cannot fulfill this requirement since it uses up to 13 comparisons :]

Unbonnet

Uhm.. is this some kind of homework? – Cobby

No. I have my own version in C++ if you really want to see it :) – Unbonnet

I'm curious, if readability is so important, then why maintain the constraint to use only 6 comparisons? ;) That kind of gimmicks is usually at odds with readability. – India

Is there some reason to not just use a sortable list? – Synonymize

@Vojislav That's what make it hard to do. I see the "pseudo code" of this med of five using 6 comparisons all around but never see the nicely implemented code in any language. It would be great if SO people can give a nice implementation. – Unbonnet

@Synonymize It would make the problem not very challenging and I'm not sure if the underlying mechanism of built-in sorting takes more than 6 comparisons. – Unbonnet

If you just want the algorithm, it would be the same as the C++ algorithm that you already have. If you want the language specific most readable solution, then use something that sorts. – Synonymize

@Synonymize What I want is not the algorithm. But the implementation that looks nice. – Unbonnet

Sounds like 'plzsendtehcodez' or 'homework' to me. – Mastodon

I'm glad I didn't do CS at school if this is the kind of homework you get – Ultramicroscopic

This is NOT a homework questions, I swear T_T. Why would the professor want a readable code in C# instead of just an pseudo code algorithm ? – Unbonnet

So if you have pretty much already figured it out, why not post your code and just ask for advice on refactoring it? – Synonymize

@Synonymize I just don't wanna show my "awkward" code. But if you think it is the way it should be I will give it a try – Unbonnet

@ Vojislav Stojkovic: actually, 6 comparisions is a sharp lower bound. just draw some hasse diagrams and you'll see there is no way of making less comparisions... – Isbella

std::swap will help make your C++ code shorter and more readable... – Caudal

Answer 1

This is basically just factoring out the swapping and sorting code from your C++ example:

private static void Swap(ref double a, ref double b) {
    double t = a;
    a = b;
    b = t;
}

private static void Sort(ref double a, ref double b) {
    if (a > b) {
        double t = a;
        a = b;
        b = t;
    }
}

private static double MedianOfFive(double a, double b, double c, double d, double e){
    // makes a < b and c < d
    Sort(ref a, ref b);
    Sort(ref c, ref d);

    // eleminate the lowest
    if (c < a) {
        Swap(ref b, ref d);
        c = a;
    }

    // gets e in
    a = e;

    // makes a < b
    Sort(ref a, ref b);

    // eliminate another lowest
    // remaing: a,b,d
    if (a < c) {
        Swap(ref b, ref d);
        a = c;
    }

    return Math.Min(d, a);
}

Ingeborg

Nice improvement of clarity, and any compiler worth anything would inline Swap and Sort if this was being used in a tight loop (the only reason I can see to implement something so specific). – Nomothetic

I find your code to be the most compact code here and mark it as accepted answer. Other code are also helpful as well, and I vote them all up :) – Unbonnet

This code is correct, but the comment // makes a < b and b < d is wrong; if you check after that sort you'll see that sometimes b > d. For example, this happens when you call MedianOfFive(1, 2, 3, 4, 5) and generally whenever e is the largest of the five arguments. – Alga

@Jason, good catch. I just copied the comments from the OP's code without checking them to see if they made sense. – Ingeborg

Answer 2

I found this post interesting and as an exercise I created this which ONLY does 6 comparisons and NOTHING else:

static double MedianOfFive(double a, double b, double c, double d, double e)
{
    return b < a ? d < c ? b < d ? a < e ? a < d ? e < d ? e : d
                                                 : c < a ? c : a
                                         : e < d ? a < d ? a : d
                                                 : c < e ? c : e
                                 : c < e ? b < c ? a < c ? a : c
                                                 : e < b ? e : b
                                         : b < e ? a < e ? a : e
                                                 : c < b ? c : b
                         : b < c ? a < e ? a < c ? e < c ? e : c
                                                 : d < a ? d : a
                                         : e < c ? a < c ? a : c
                                                 : d < e ? d : e
                                 : d < e ? b < d ? a < d ? a : d
                                                 : e < b ? e : b
                                         : b < e ? a < e ? a : e
                                                 : d < b ? d : b
                 : d < c ? a < d ? b < e ? b < d ? e < d ? e : d
                                                 : c < b ? c : b
                                         : e < d ? b < d ? b : d
                                                 : c < e ? c : e
                                 : c < e ? a < c ? b < c ? b : c
                                                 : e < a ? e : a
                                         : a < e ? b < e ? b : e
                                                 : c < a ? c : a
                         : a < c ? b < e ? b < c ? e < c ? e : c
                                                 : d < b ? d : b
                                         : e < c ? b < c ? b : c
                                                 : d < e ? d : e
                                 : d < e ? a < d ? b < d ? b : d
                                                 : e < a ? e : a
                                         : a < e ? b < e ? b : e
                                                 : d < a ? d : a;
}

Linette

Cool! Glad you have find this question useful :) – Unbonnet

Very nice, but not necessarily the fastest when compiled. Anyway, for the records, for unsigned char data type, SSE implementation (to be used for image processing) turned out to be about 60 times faster, on i7 processor. – Pronto

Answer 3

Thanks. I know your posts are quite old, but it was useful for my issue.

I needed a way to compute the median of 5 SSE/AVX registers (4 floats / 8 floats at once, or 2 doubles/4 doubles at once):

• without any conditional jumps

• only with min/max instructions

If the min/max functions are programmed for scalar registers with conditional jumps, my code is not optimal in term of comparisons. But if the min/max functions are coded with corresponding CPU instructions, my code is very effective because no conditional jump is done by the CPU when executing.

    template<class V> 
    inline V median(const V &a, const V &b, const V &c)
    {
      return max(min(a,b),min(c,max(a,b))); 
    } 

    template<class V> 
    inline V median(const V &a, const V &b, const V &c, const V &d, const V &e)
    {
      V f=max(min(a,b),min(c,d)); // discards lowest from first 4
      V g=min(max(a,b),max(c,d)); // discards biggest from first 4
      return median(e,f,g);
    } 

Comforter

Exactly what I was looking for! I was stuck on how to compute the median of three values with min max, too bad it requires 4 operations! – Pronto

@Antonio: Fastest way of finding the middle value of a triple? Here's median5() that uses min/max CPU instructions (combines this and @Gyorgy Szekely code). Test for median5() in Python (just in case) – Lanthanide

@Lanthanide Amazing! It looks good to me, you should publish an answer here. I have written the explicitly vectorized code, but cannot publish the code. – Pronto

Answer 4

An interesting thread here:

http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1061827085

Quote from thread:

1. Put the numbers in an array.

2. Use three comparisons and shuffle around the numbers so that a[1] < a[2], a[4] < a[5], and a[1] < a[4].

3. If a[3] > a[2], then the problem is fairly easy. If a[2] < a[4], the median value is the smaller of a[3] and a[4]. If not, the median value is the smaller of a[2] and a[5].

4. So a[3] < a[2]. If a[3] > a[4], then the solution is the smaller of a[3] and a[5]. Otherwise, the solution is the smaller of a[2] and a[4].

Mariettemarigold

This is looking great. The solution I found is also from the same thread. A solid implementation in C# would also be fine :D – Unbonnet

Answer 5

This is pretty ugly and could use some refactoring, but it explicitly walks through all the comparisons and swaps so you can see what's going on.

public double medianOfFive(double a, double b, double c, double d, double e){
    double median;
    // sort a and b
    if(a > b) // comparison # 1
    {
        double temp = a;
        a = b;
        b = temp;
    }

    // sort c and d
    if(c > d)  // comparison # 2
    {
        double temp = c;
        c = d;
        d = temp;
    }

    // replace the lower of a and c with e
    // because the lowest of the first four cannot be the median
    if(a < c) // comparison # 3
    {
        a = e;
        // re-sort a and b
        if(a > b) // comparison # 4
        {
            double temp = a;
            a = b;
            b = temp;
        }
    }
    else
    {
        c = e;
        // re-sort c and d
        if(c > d)  // comparison # 4
        {
            double temp = c;
            c = d;
            d = temp;
        }
    }

    // eliminate a or c, because the lowest
    // of the remaining four can't be the median either
    if(a < c) // comparison #5
    {
         if(b < c) // comparison #6
         {
              median = c;
         }
         else
         {
              median = b;
         }
    }
    else
    {
         if(d < a) // comparison #6
         {
              median = a;
         }
         else
         {
              median = d;
         }
    }
    return median;
}

Concave

Answer 6

Just to check how many comparisons:

    class MyComparable : IComparable
{

    public static int NumberOfComparisons = 0;

    public int NumPart { get; set; }

    #region IComparable Members

    public int CompareTo(object obj)
    {
        NumberOfComparisons++; //I know, not thread safe but just for the sample
        MyComparable mc = obj as MyComparable;
        if (mc == null)
            return -1;
        else
            return NumPart.CompareTo(mc.NumPart);
    }

    #endregion
}

class Program
{
    static void Main(string[] args)
    {
        List<MyComparable> list = new List<MyComparable>();
        list.Add(new MyComparable() { NumPart = 5 });
        list.Add(new MyComparable() { NumPart = 4 });
        list.Add(new MyComparable() { NumPart = 3 });
        list.Add(new MyComparable() { NumPart = 2 });
        list.Add(new MyComparable() { NumPart = 1 });
        list.Sort();


        Console.WriteLine(MyComparable.NumberOfComparisons);
    }
}

the result is 13.

Peers

Answer 7

For completeness, the question is a specific case of a sorting network, which Knuth (Art of Computer Programming, vol 3) covers in great detail. The classic paper by K.E. Batcher on the subject is brief and worth reading.

Corker

Answer 8

This should do it

private Double medianofFive(double[] input)
{
    Double temp;
if (input[0] > input[1])//#1 - sort First and Second
{
    temp = input[0];
    input[0] = input[1];
    input[1] = temp;
}
if (input[2] > input[3])//#2 sort Third and Fourth
{
    temp = input[2];
    input[2] = input[3];
    input[3] = temp;
}

// replace the smaller of first and third with 5th, then sort
int smallerIndex = input[0] < input[2] ? 0 : 2;//#3
input[smallerIndex] = input[4];

//sort the new pair
if(input[smallerIndex]>input[smallerIndex+1])//#4
{
    temp = input[smallerIndex];
    input[smallerIndex] = input[smallerIndex+1];
    input[smallerIndex+1] = temp;
}

//compare the two smaller numbers
// then compare the smaller of the two's partner with larger of the two
// the smaller of THOSE two is the median
if (input[2] > input[0])
//#5
{
    temp = input[2] > input[1] ? input[1] : input[2];//#6
}
else
{
    temp = input[0] > input[3] ? input[3] : input[0];//#6
}
    return temp;
}

Scrim

Don't know what's going on, but it looks fine in preview, but gets cut off on the main page – Scrim

Fixed. Use the markdown editor, not your own form of markdown. – Corncob

Answer 9

Here's a bit of a variant on the other answers, which provides on average from 3.33% to 66.67% improvement over 6 comparisons, and fully partitions the 5 elements around their median as a bonus at no extra cost.

It's possible to find the median of 5 distinct elements in an average of 5.8 comparisons (averaged over all permutations) by using median-of-3 and quickselect, using median-of-3 to select the pivot from a sample of 3 of the 5 elements. Median-of-3 partitions those three elements, which need not be recompared to the pivot when partitioning the remaining 2 elements. So far that's 4-5 comparisons to partition the 5 elements around one of the three middle elements (the median-of-3 cannot be either the minimum or maximum of 5). Up to 3 more comparisons may be necessary to partition the 5 elements around their median (which strictly speaking is more work than merely finding the median), for a total ranging from 4 to 7 comparisons, with (as mentioned) an average of 5.8 over all possible permutations of 5 distinct elements (fewer comparisons if the elements are not distinct). Note that this differs from the usual always-6-comparisons solutions, in that a few cases of distinct inputs may require as many as 7 comparisons, but on the other hand, most permutations of distinct inputs require no more than 6, and often fewer; moreover it is fairly easy to code to save comparisons for non-distinct inputs (only 2 comparisons are required if all inputs are equal; the code to save comparisons when inputs are not distinct using the usual 6-comparison method becomes rather convoluted (try it!), and without that it still takes 6 comparisons even when all inputs are equal).

Order statistics other than the median can be found this way: the 2nd smallest or 2nd largest can be found in on average slightly more (5.81666... comparisons), and of course it's possible to find the minimum or maximum with only 4 comparisons.

Based on that, and by request, here's a heavily commented function to return a pointer to the median of 5 elements, using a variadic comparison function. It's written in C, but it should work just as well in the quadrathorpe-y deviant or in sea ploose ploose. Note that this returns a pointer to the median-valued element only; it does not partition the elements (in fact it doesn't move any elements).

/* a virtual swap, preserving both pointers for later use */
#define VSWAP(ma,mb,mt) mt=ma,ma=mb,mb=mt
/* a virtual swap only preserving the first pointer */
#define VSWAP2(ma,mb,munused) ma=mb
/* virtual rotation to the left; reverse the first 3 args for right rotation */
#define ROTATE(ma,mb,mc,mt) (mt)=(ma),(ma)=(mb),(mb)=(mc),(mc)=(mt)


/* median of 5 elements, no data movement, minimum (average 5.8) comparisons */
/* This implementation minimizes the number of comparisons made (min. 2) when
   elements compare equal.
*/
/* As no elements are moved, the elements are of course not partitioned around
   the element pointed to by the returned pointer (this differs from selection
   of the median via quickselect).
*/
/* Results are biased toward the middle: pc, then pb or pd, last pa or pe. */
/* The implementation is based on a simulation of quickselect using partition3
   to select a pivot from the middle three elements, with partitioning by
   skipping over the 3 partitioned elements.  For distinct inputs, it uses on
   average 5.8 comparisons (averaged over all permutations of 5 distinct
   elements); fewer for inputs with equal elements.  That's an improvement of
   about 3% over the usual 6-comparison implementation of median-of-5.
*/
void *fmed5(void *pa, void *pb, void *pc, void *pd, void *pe,
    int(*compar)(const void *,const void *))
{
    void *t;
    int c, d;
    /* First compare the 3 middle elements to determine their relative
       ordering; pb will point to the minimum, pc to the median, and pd to
       the maximum of the three.
    */
    /* Ternary median-of-3, biased toward middle element if possible, else
       first element.  Average 8/3 comparisons for 3 elements (distinct values)
       = 0.889 comparisons/element
    */
    c=compar(pb,pc); /* 1 */
    if (0<c) { /* *pb,*pc out-of-order: *pb>*pc */
        /* Before doing anything about pb,pc, compare *pc,*pd. */
        d=compar(pc,pd); /* 2a */
        if (0>d) { /* *pc<*pd: strictly in order */
            /* But *pb might be either larger than or smaller than (or equal
               to) *pd, so they may (i.e. unless it's known from the earlier
               comparison of original *pc and *pd that *pb is larger than
               both) have to be compared,  Possibilities:
               *pc<*pb<=*pd (virtual swap of pb,pc corrects relationship)
               *pc<*pd<*pb (virtual rotation to the left corrects it)
            */
            c=compar(pb,pd); /* 3a (if needed) */
            if (0<c) { /* *pc < *pd < *pb */
                ROTATE(pb,pc,pd,t);
            } else { /* *pc < *pb <= *pd */
                VSWAP(pb,pc,t);
            }
        } else { /* *pd==*pc<*pb or reversed ordering: *pd<*pc<*pb */
            VSWAP(pb,pd,t); /* one (virtual) swap takes care of it */
        } /* *pc:*pd comparisons results if-else */
        /* Note that if pc,pd compare equal, pc remains as the chosen
           median (biased toward the middle element).
        */
    } else if (0==c) { /* *pb,*pc compare equal */
        /* Either pb or pc can be taken as the median; bias here is towards
           pc, which is already in the middle position. But pd might be
           the minimum of the three or the maximum (or it may also be equal
           to both pb and pc).
        */
        d=compar(pb,pd); /* 2b */
        if (0<d) { /* pb,pd are out-of-order */
            VSWAP(pb,pd,t);
        }
    } else { /* *pb,*pc in strict order: *pb < *pc; how about *pc,*pd? */
        d=compar(pc,pd); /* 2c */
        if (0<d) { /* *pc,*pd are strictly out-of-order: *pd < *pc */
            /* But *pb might be either larger than or smaller than (or equal
               to) *pd, so they may (i.e. unless it's known from the earlier
               comparison of original *pc and *pd that *pb is larger than
               both) have to be compared,  Possibilities:
               *pb<=*pd<*pc (virtual swap of pc,pd corrects relationship)
               *pd<*pb<*pc (virtual rotation to the right corrects it)
            */
            c=compar(pb,pd); /* 3b (if needed) */
            if (0<c) { /* *pd < *pb < *pc */
                ROTATE(pd,pc,pb,t);
            } else { /* *pc < *pb <= *pd */
                VSWAP(pc,pd,t);
            }
        } /* *pc:*pd comparisons results if-else */
        /* Note that if pc,pd compare equal, pc remains as the chosen
           median (biased toward the middle element).
        */
    } /* *pb:*pc comparisons results if-else chain */
    /* Now pb points to the minimum of pb,pc,pd; pc to the median, and pd
       to the maximum.
    */
    /* Special case: if all three middle elements compare equal (0==c==d),
       any one can be returned as the median of 5, as it's impossible for
       either of the other two elements to be the median (unless of course
       one or both of them also compares equal to pb,pc,pd, in which case
       returning any of pb,pc,pd is still correct).  Nothing more needs to
       be done in that case.
    */
    if ((0!=c)||(0!=d)) { /* Not all three of pb,pc,pd compare equal */
        int e;
        /* Compare pa and pe to pc. */
        e=compar(pa,pc); /* 3c or 4a (iff needed) */
        /* If three (or more) of the four elements so far compared are
           equal, any of those equal-comparing elements can be chhosen as
           the median of 5.  If all five elements were arranged in order,
           one of the three equal-comparing elements would necessarily be
           in the middle (at most both of the remaining elements might be
           either larger or smaller than the equal elements).  So if pa
           compares equal to pc and pc also compared equal to pb or to pd,
           nothing more need be done; pc can be considered as the median of
           five.
        */
        if ((0!=e)||(0!=c)||(0!=d)) { /* no three elements compare equal */
            int f;
            f=compar(pe,pc); /* 4b or 5a (iff needed) */
            /* Check again for three equal comparisons to avoid doing any
               unnecessary additional work.
            */
            if (
                (0!=f) /* also not equal; still not three */
              ||
                ( /* 0==f && */
                 ((0!=c)&&(0!=d)) /* at most e and f; not three */
               ||
                 ((0!=c)&&(0!=e)) /* at most d and f; not three */
               ||
                 ((0!=d)&&(0!=e)) /* at most c and f; not three */
                )
            ) {
                /* Possibilites are that:
                     one of *pa,*pe is less than (or equal to) *pc and one
                       is greater than (or equal to) *pc; *pc is the median
                       of five.
                     *pa and *pe are both less than *pc; the median of five
                       is then the maximum of *pa,*pb,*pe (*pc and *pd are
                       at least as large as those three).  The ordering of
                       those 3 elements has not been established, and it
                       will take two additional comparisons to do so.
                     *pa and *pe are both greater than *pc; the median of
                       five is the minimum of *pa,*pd,*pe (neither *pb nor
                       *pc can be larger than any of those three).
                */
                if ((0<e)&&(0<f)) { /* *pa,*pe both > *pc; median of five is
                                       the minimum of *pa,*pe,*pd
                                    */
                    /* Bias towards *pd (originally closest of these three
                       to the middle.  Neither *pa nor *pe has yet been
                       compared to *pd.
                    */
                    e=compar(pa,pe); /* 5b or 6a (iff needed) */
                    if (0<e) { /* *pe is smaller */
                        f=compar(pd,pe); /* 6b or 7a (iff needed) */
                        if (0<f) { /* *pe is smaller */
                            VSWAP2(pc,pe,t);
                        } else { /* *pd is smaller or *pd==*pe */
                            VSWAP2(pc,pd,t);
                        }
                    } else { /* *pa==*pe or *pa is smaller */
                        f=compar(pd,pa); /* 6c or 7b (iff needed) */
                        if (0<f) { /* *pa is smaller */
                            VSWAP2(pc,pa,t);
                        } else { /* *pd is smaller or *pd==*pa */
                            VSWAP2(pc,pd,t);
                        }
                    }
                } else if ((0>e)&&(0>f)) { /* *pa,*pe both < *pc; median of
                                       five is the maximum of *pa,*pb,*pe
                                    */
                    /* Bias towards *pb (originally closest of these three
                       to the middle.  Neither *pa nor *pe has yet been
                       compared to *pb.
                    */
                    e=compar(pa,pe); /* 5c or 6d (iff needed) */
                    if (0<e) { /* *pa is larger */
                        f=compar(pa,pb); /* 6e or 7c (iff needed) */
                        if (0<f) { /* *pa is larger */
                            VSWAP2(pc,pa,t);
                        } else { /* *pb is larger or *pa==*pb */
                            VSWAP2(pc,pb,t);
                        }
                    } else { /* *pe is larger or *pa==*pe */
                        f=compar(pe,pb); /* 6f or 7d (iff needed) */
                        if (0<f) { /* *pe is larger */
                            VSWAP2(pc,pe,t);
                        } else { /* *pb is larger or *pe==*pb */
                            VSWAP2(pc,pb,t);
                        }
                    } /* *pa:*pe results if-else */
                } /* median of five: minimum or maximum of three if-else */
            } /* not three equal elements among five */
        } /* not three equal elements among four */
    } /* not three equal elements among three */
    return pc;
}

Delete

Answer 10

Coding isn't really my thing, but here's the algorithm I would use expressed in natural language. Let's denote these five numbers by a, b, c, d, and e.

Compare a and b, c and d. WLOG let a < b, c < d. (2 comparisons so far)

Compare a and c. WLOG let a < c. (3)

Compare b and e. (4) Note that b is used instead of d (and they cannot be swapped) because b is the "counterpart" of the smaller of a and c.

Case 1: let b < e.

____Compare b and c — the greater value is the median. (5)

Case 2: let b > e.

____Compare a and e. (5)

____Case 2.1: let a < e.

________Compare c and e — the greater value is the median. (6)

____Case 2.2: let a > e.

________Compare b and c — the smaller value is the median. (6)

(Formatting is ugly ik >.<)

Coates

The question was how to do it in C#. This answer describes how to do it in psuedo code. There are other answers that describe how to do it in C#. – Ferity

This does not provide an answer to the question. Once you have sufficient reputation you will be able to comment on any post; instead, provide answers that don't require clarification from the asker. - From Review – Martinet

Answer 11

Interesting how many comparisons in MSDN sample...

public static double Median(this IEnumerable<double> source) {
        if (source.Count() == 0)  throw new InvalidOperationException("Cannot compute median for an empty set.");

        var sortedList = from number in source
                         orderby number
                         select number;

        int itemIndex = (int)sortedList.Count() / 2;

        if (sortedList.Count() % 2 == 0) {
            // Even number of items.
            return (sortedList.ElementAt(itemIndex) + sortedList.ElementAt(itemIndex - 1)) / 2; } else {
            // Odd number of items.
            return sortedList.ElementAt(itemIndex); }
    }

Prot