Reliability of Two-Terminal Networks Equivalent to Small Optimal Sorting Nets

Sorting networks are a special case of “oblivious” sorting algorithms that can be implemented directly in hardware. Their underlying non-plane connectivity graph representations can be mapped onto a certain class of minimal two-terminal networks, allowing us to associate a two-terminal reliability polynomial to any (optimal) sorting network connectivity graph. This class of networks is interesting in that it intersects the class of “matchstick minimal” two-terminal networks (which includes the planar Moore-Shannon hammocks), yet neither of these two classes contains the other. We compare the two-terminal reliability polynomials associated in this manner to small optimal sorting network connectivity graphs, with the reliability polynomials of Moore-Shannon hammock networks of equivalent dimensions.