Optimal 9-element sorting network that reduces to an optimal median-of-9 network?

Question

I am looking into sorting and median-selection networks for nine elements based exclusively on two-input minimum / maximum operations. Knuth, TAOCP Vol. 3, 2nd ed. states (page 226) that a nine-element sorting network requires at least 25 comparisons, which translates into an equal number of SWAP() primitives or 50 min / max operations. Obviously a sorting network can be converted into a median-selection network by eliminating redundant operations. The conventional wisdom seems to be that this does not result in an optimal median-selection network. While this seems to be empirically true, I can find no proof in the literature that this is necessarily so.

Lukáŝ Sekanina, "Evolutionary Design Space Exploration for Median Circuits". In: EvoWorkshops, March 2004, pp. 240-249, gives the minimal number of min / max operations required for an optimal nine-input median-selection network as 30 (table 1). I verified that this is achieved both by the well-known median-selection network given by John L. Smith, "Implementing median filters in XC4000E FPGAs". XCELL magazine, Vol. 23, 1996, p. 16, and the median-of-9 network from the earlier work of Chaitali Chakrabarti and Li-Yu Wang, "Novel sorting network-based architectures for rank order filters." IEEE Transactions on Very Large Scale Integration Systems, Vol. 2, No. 4 (1994), pp. 502-507, where the latter converts into the former by simple elimination of redundant components. See variants 4 and 5 in the code below.

Examining published optimal nine-element sorting networks for suitability for conversion into efficient median-selection networks through elimination of redundant operations, the best version I managed to find is from John M. Gamble's online generator, which requires 32 min / max operations, so just two shy of the optimal operation count. This is shown as variant 1 in the code below. Other optimal sorting networks reduce to 36 min / max operations (variant 2) and 38 min / max operations (variant 3), respectively.

Is there any known nine-element sorting network (i.e. with 50 two-input min / max operations) which reduces to an optimal nine-input median-selection network (with 30 two-input min / max operations) through elimination of redundant operations alone?

The code below uses float data as a test case, since many processors offer minimum / maximum operations for floating-point data but not integer data, GPUs being one exception. Due to issues with special floating-point operands (which do not occur in my actual use case), optimal code sequences typically require the use of "fast math" modes offered by compilers, such as in this Godbolt testbed.

#include <cstdlib>
#include <cstdio>
#include <algorithm>

#define VARIANT     1
#define FULL_SORT   0

typedef float T;

#define MIN(a,b) std::min(a,b)
#define MAX(a,b) std::max(a,b)
#define SWAP(i,j) do { T s = MIN(a##i,a##j); T t = MAX(a##i,a##j); a##i = s; a##j = t; } while (0)
#define MIN3(x,y,z)  MIN(a##x,MIN(a##y,a##z))
#define MAX3(x,y,z)  MAX(a##x,MAX(a##y,a##z))
#define MED3(x,y,z)  MIN(MAX(MIN(a##y,a##z),a##x),MAX(a##y,a##z))
#define SORT3(x,y,z) do { T s = MIN3(x,y,z);  T t = MED3(x,y,z);  T u = MAX3(x,y,z); a##x=s; a##y=t; a##z=u; } while (0)

/* Use sorting/median network to fully or partially sort array of nine values
   and return the median value
*/
T network9 (T *a)
{
    // copy to scalars
    T a0, a1, a2, a3, a4, a5, a6, a7, a8;
    a0=a[0];a1=a[1];a2=a[2];a3=a[3];a4=a[4];a5=a[5];a6=a[6];a7=a[7];a8=a[8];

#if VARIANT == 1
    // Full sort. http://pages.ripco.net/~jgamble/nw.html
    SWAP (0, 1);   SWAP (3, 4);   SWAP (6, 7);   SWAP (1, 2);   SWAP (4, 5);
    SWAP (7, 8);   SWAP (0, 1);   SWAP (3, 4);   SWAP (6, 7);   SWAP (0, 3);
    SWAP (3, 6);   SWAP (0, 3);   SWAP (1, 4);   SWAP (4, 7);   SWAP (1, 4);
    SWAP (2, 5);   SWAP (5, 8);   SWAP (2, 5);   SWAP (1, 3);   SWAP (5, 7);
    SWAP (2, 6);   SWAP (4, 6);   SWAP (2, 4);   SWAP (2, 3);   SWAP (5, 6);
#elif VARIANT == 2
    // Full sort. Donald E. Knuth, TAOCP Vol. 3, 2nd ed., Fig 51
    SWAP (0, 1);   SWAP (3, 4);   SWAP (6, 7);   SWAP (1, 2);   SWAP (4, 5);
    SWAP (7, 8);   SWAP (0, 1);   SWAP (3, 4);   SWAP (6, 7);   SWAP (2, 5);
    SWAP (0, 3);   SWAP (5, 8);   SWAP (1, 4);   SWAP (2, 5);   SWAP (3, 6);
    SWAP (4, 7);   SWAP (0, 3);   SWAP (5, 7);   SWAP (1, 4);   SWAP (2, 6);
    SWAP (1, 3);   SWAP (2, 4);   SWAP (5, 6);   SWAP (2, 3);   SWAP (4, 5);
#elif VARIANT == 3
    // Full sort. Vinod K Valsalam and Risto Miikkulainen, "Using Symmetry 
    // and Evolutionary Search to Minimize Sorting Networks". Journal of 
    // Machine Learning Research 14 (2013) 303-331
    SWAP (2, 6);   SWAP (0, 5);   SWAP (1, 4);   SWAP (7, 8);   SWAP (0, 7);
    SWAP (1, 2);   SWAP (3, 5);   SWAP (4, 6);   SWAP (5, 8);   SWAP (1, 3);
    SWAP (6, 8);   SWAP (0, 1);   SWAP (4, 5);   SWAP (2, 7);   SWAP (3, 7);
    SWAP (3, 4);   SWAP (5, 6);   SWAP (1, 2);   SWAP (1, 3);   SWAP (6, 7);
    SWAP (4, 5);   SWAP (2, 4);   SWAP (5, 6);   SWAP (2, 3);   SWAP (4, 5);
#elif VARIANT == 4
    // Chaitali Chakrabarti and Li-Yu Wang, "Novel sorting network-based 
    // architectures for rank order filters." IEEE Transactions on Very
    // Large Scale Integration Systems, Vol. 2, No. 4 (1994), pp. 502-507
    // sort columns
    SORT3 (0, 1, 2);
    SORT3 (3, 4, 5);
    SORT3 (6, 7, 8);
    // sort rows
    SORT3 (0, 3, 6);  // degenerate: MAX3 -> a6
    SORT3 (1, 4, 7);  // degenerate: MED3 -> a4
    SORT3 (2, 5, 8);  // degenerate: MIN3 -> a2
    // median computation
    SORT3 (2, 4, 6);  // degenerate: MED3 -> a4 has rank 4
#elif VARIANT == 5
    // John L. Smith, "Implementing median filters in XC4000E FPGAs", 
    // XCELL magazine, Vol. 23, 1996, p. 16
    SORT3 (0, 1, 2);
    SORT3 (3, 4, 5);
    SORT3 (6, 7, 8);
    a3 = MAX3 (0, 3, 6);  // a3 has rank 2,3,4,5,6
    a4 = MED3 (1, 4, 7);  // a4 has rank 3,4,5
    a5 = MIN3 (2, 5, 8);  // a5 has rank 2,3,4,5,6
    a4 = MED3 (3, 4, 5);  // a4 has rank 4
#else 
#error unknown VARIANT
#endif

#if FULL_SORT
    // copy back sorted results
    a[0]=a0;a[1]=a1;a[2]=a2;a[3]=a3;a[4]=a4;a[5]=a5;a[6]=a6;a[7]=a7;a[8]=a8;
#endif

    // return median-of-9
    return a4;
}

Answer 1

I'm not sure this will meet all the criteria for what you're looking for, but here's a way to transform variant 5 into a 25-swap, 50-min/max sorting network, and then reduce it to a 30-min/max median-selection network:

We start with the median-selection network (John L. Smith, 1996) which uses three SORT3's, one MAX3, one MIN3 and two MED3's:

We change all the MAX3, MIN3 and MED3's into SORT3's, and add four SWAP's to get a full sorting network:

(We don't need full sorting of triples 1,2,3 and 5,6,7 at the end, because 2 cannot be less than both 1 and 3, and 6 cannot be greater than both 5 and 7.)

When we replace the SORT3's by SWAP's, we get this standard 25-swap sorting network:

We can then reduce it to this 30-min/max median-selection network:

MIN = Math.min; MAX = Math.max;

function sortingNetwork9(a) {        // 50x min/max
    swap(0,1); swap(3,4); swap(6,7);
    swap(1,2); swap(4,5); swap(7,8);
    swap(0,1); swap(3,4); swap(6,7);
    swap(0,3); swap(3,6); swap(0,3);
    swap(1,4); swap(4,7); swap(1,4);
    swap(5,8); swap(2,5); swap(5,8);
    swap(2,4); swap(4,6); swap(2,4);  
    swap(1,3); swap(2,3);
    swap(5,7); swap(5,6);

    function swap(i,j) {var tmp = MIN(a[i],a[j]); a[j] = MAX(a[i],a[j]); a[i] = tmp;}
}
function medianSelection9(a) {       // 30x min/max
    swap(0,1); swap(3,4); swap(6,7);
    swap(1,2); swap(4,5); swap(7,8);
    swap(0,1); swap(3,4); swap(6,7);
     max(0,3);  max(3,6);  // (0,3);
    swap(1,4);  min(4,7);  max(1,4);
     min(5,8);  min(2,5);  // (5,8);
    swap(2,4);  min(4,6);  max(2,4);  
     // (1,3);  // (2,3);
     // (5,7);  // (5,6);

    function swap(i,j) {var tmp = MIN(a[i],a[j]); a[j] = MAX(a[i],a[j]); a[i] = tmp;}
    function min(i,j) {a[i] = MIN(a[i],a[j]);}
    function max(i,j) {a[j] = MAX(a[i],a[j]);}
}
var a = [5,7,1,8,2,3,6,4,0], b = [5,7,1,8,2,3,6,4,0];
sortingNetwork9(a);
medianSelection9(b);
document.write("sorted: " + a + "<br>median: " + b[4]);