Best Sort function for short arrays

Question

I'm working on an algorithm that manipulates pictures. Basically I will implement a diffusion (each pixel will get the median value of the 8 surrounding pixels + its own value).

what I will do is to create a array of 9 integers with the value, sort the array and get the median value at array[4].

I still don't know what to use for the problem, what is the best sorting function to use for relatively small arrays? The sorting function will roughly be called x times, x being the number of pixels.

Heapsort seems a bit overkill. Quicksort will not perform that well. And I don't want to implement really complex things.

What do you guys think?

Answer 1

If all you need is the median, there's no need to do any sorting at all! (For long arrays, see http://en.wikipedia.org/wiki/Selection_algorithm for an O(n) algorithm; of course we're talking only about short arrays here).

For median of 9 numbers, a little googling reveals the article Fast median search: an ANSI C implementation by N. Devillard, which points to the article Implementing median filters in XC4000E FPGAs by J. L. Smith, which provides this self-explanatory "sorting network" to get the median using 19 comparisons:

In terms of C:

typedef int T;

void sort2(T* a, T* b);
void sort3(T* a, T* b, T* c);
T min3(T a, T b, T c);
T max3(T a, T b, T c);

T median9(T p1, T p2, T p3, T p4, T p5, T p6, T p7, T p8, T p9)
{
    sort3(&p1, &p2, &p3);
    sort3(&p4, &p5, &p6);
    sort3(&p7, &p8, &p9);

    p7 = max3(p1, p4, p7);
    p3 = min3(p3, p6, p9);

    sort3(&p2, &p5, &p8);
    sort3(&p3, &p5, &p7);

    return p5;
}

void sort2(T* a, T* b)
{
    if (*a > *b)
    {
        T tmp = *b;
        *b = *a;
        *a = tmp;
    }
}

void sort3(T* a, T* b, T* c)
{
    sort2(b, c);
    sort2(a, b);
    sort2(b, c);
}

T min3(T a, T b, T c)
{
    if (a < b)
        return a < c ? a : c;
    else
        return b < c ? b : c;
}

T max3(T a, T b, T c)
{
    if (a > b)
        return a > c ? a : c;
    else
        return b > c ? b : c;
}

---

Edit: this file also contains the code for getting the median of 3, 5, 6, 7, 9 and 25 numbers.

#define PIX_SORT(a,b) { if ((a)>(b)) PIX_SWAP((a),(b)); }
#define PIX_SWAP(a,b) { pixelvalue temp=(a);(a)=(b);(b)=temp; }

/*----------------------------------------------------------------------------
   Function :   opt_med9()
   In       :   pointer to an array of 9 pixelvalues
   Out      :   a pixelvalue
   Job      :   optimized search of the median of 9 pixelvalues
   Notice   :   in theory, cannot go faster without assumptions on the
                signal.
                Formula from:
                XILINX XCELL magazine, vol. 23 by John L. Smith

                The input array is modified in the process
                The result array is guaranteed to contain the median
                value
                in middle position, but other elements are NOT sorted.
 ---------------------------------------------------------------------------*/

pixelvalue opt_med9(pixelvalue * p)
{
    PIX_SORT(p[1], p[2]) ; PIX_SORT(p[4], p[5]) ; PIX_SORT(p[7], p[8]) ;
    PIX_SORT(p[0], p[1]) ; PIX_SORT(p[3], p[4]) ; PIX_SORT(p[6], p[7]) ;
    PIX_SORT(p[1], p[2]) ; PIX_SORT(p[4], p[5]) ; PIX_SORT(p[7], p[8]) ;
    PIX_SORT(p[0], p[3]) ; PIX_SORT(p[5], p[8]) ; PIX_SORT(p[4], p[7]) ;
    PIX_SORT(p[3], p[6]) ; PIX_SORT(p[1], p[4]) ; PIX_SORT(p[2], p[5]) ;
    PIX_SORT(p[4], p[7]) ; PIX_SORT(p[4], p[2]) ; PIX_SORT(p[6], p[4]) ;
    PIX_SORT(p[4], p[2]) ; return(p[4]) ;
}