Number of comparisons made in median of 3 function?

Question

As of right now, my functioin finds the median of 3 numbers and sorts them, but it always makes three comparisons. I'm thinking I can use a nested if statement somewhere so that sometimes my function will only make two comparisons.

int median_of_3(int list[], int p, int r)
{
    int median = (p + r) / 2;

    if(list[p] > list[r])
        exchange(list, p, r);
    if(list[p] > list[median])
        exchange(list, p, median);
    if(list[r] > list[median])
        exchange(list, r, median);

    comparisons+=3;                // 3 comparisons for each call to median_of_3

    return list[r];
}

I'm not sure I see where I can make that nested if statement.

Answer 1

If you only need the median value, here's a branch-less solution based on min/max operators:

median = max(min(a,b), min(max(a,b),c));

Intel CPU's have SSE min/max vector instructions, so depending on your or your compiler's ability to vectorize, this can run extremely fast.

Answer 2

If we allow extra operations, we could use at most 2 comparisons to find the median. The trick is to use exclusive or to find the relationship among three numbers.

void median3(int A[], int p, int r)
{
    int m = (p+r)/2;
    /* let a, b, c be the numbers to be compared */
    int a = A[p], b = A[m], c = A[r];
    int e = a-b;
    int f = a-c;

    if ((e^f) < 0) {
        med_comparisons += 1;
        /* a is the median with 1 comparison */
        A[m] = a;
        /* b < a < c ? */
        if (b < c) /* b < a < c */ { A[p] = b, A[r] = c; }
        else       /* c < a < b */ { A[p] = c, A[r] = b; }
        comparisons += 2;
    } else {
        med_comparisons += 2;
        int g = b-c;
        if ((e^g) < 0) {
            /* c is the median with 2 comparisons */ 
            A[m] = c;
            /* a < c < b ? */
            if (a < b) /* a < c < b */ { A[p] = a, A[r] = b; }
            else       /* b < c < a */ { A[p] = b, A[r] = a; }
        } else {
            /* b is the median with 2 comparisons */
            A[m] = b;
            /* c < b < a ? */
            if (a > c) /* c < b < a */ { A[p] = c; A[r] = a; }
            else       /* a < b < c */ { /* do nothing */    }
        }
        comparisons += 3;
    }
}

The first exclusive or (e^f) is to find out the difference of the sign bit between (a-b) and (a-c).
If they have different sign bit, then a is the median. Otherwise, a is either the minimum or the maximum. In that case, we need the second exclusive or (e^g).

Again, we are going to find out the difference of the sign bit between (a-b) and (b-c). If they have different sign bit, one case is that a > b && b < c. In this case, we also get a > c because a is the maximum in this case. So we have a > c > b. The other case is a < b && b > c && a < c. So we have a < c < b; In both cases, c is the median.

If (a-b) and (b-c) have the same sign bit, then b is the median using similar arguments as above. Experiments shows that a random input will need 1.667 comparisons to find out the median and one extra comparison to get the order.