title: Optimal 9-element sorting network that reduces to an optimal median-of-9 network?
body: <p>I am looking into sorting and median-selection networks for nine elements based exclusively on two-input minimum / maximum operations. Knuth, <em>TAOCP Vol. 3</em>, 2nd ed. states (page 226) that a nine-element sorting network requires at least 25 comparisons, which translates into an equal number of <code>SWAP()</code> 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.</p>
  
  <p>Lukáŝ Sekanina, "Evolutionary Design Space Exploration for Median Circuits". In: <em>EvoWorkshops</em>, 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". <em>XCELL magazine</em>, 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." <em>IEEE Transactions on Very Large Scale Integration Systems</em>, 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.</p>
  
  <p>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 <a href="http://pages.ripco.net/~jgamble/nw.html" rel="noreferrer">online generator</a>, 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.</p>
  
  <p>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?</p>
  
  <p>The code below uses <code>float</code> 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 <a href="https://godbolt.org/g/W5Zzrg" rel="noreferrer">Godbolt testbed</a>.</p>
  
  <pre class="lang-c++ prettyprint-override"><code>#include &lt;cstdlib&gt;
  #include &lt;cstdio&gt;
  #include &lt;algorithm&gt;
  
  #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 -&gt; a6
      SORT3 (1, 4, 7);  // degenerate: MED3 -&gt; a4
      SORT3 (2, 5, 8);  // degenerate: MIN3 -&gt; a2
      // median computation
      SORT3 (2, 4, 6);  // degenerate: MED3 -&gt; 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;
  }
  </code></pre>