# Does the 0-1 principle apply to merge networks?

For sorting networks, the 0-1 principle says that if it can sort any sequence of 0's and 1's, then it can sort any list.

What if I want to build a comparison-swap network for merging two pre-sorted lists. Can I still rely on the 0-1 principle to determine if my network is correct?

Note: If so, this means it's possible to determine whether a network is a merging network in polynomial time (since there are only polynomially-many pairs of sorted lists of zeros and ones)

$$\def\et{\mathbin\&}$$Yes, and this holds much more generally. Note that a comparator can be thought of as a pair of gates, one of which computes $$\min\{x,y\}$$, and the other $$\max\{x,y\}$$. A linearly ordered set is a distributive lattice with $$x\land y=\min\{x,y\}$$ and $$x\lor y=\max\{x,y\}$$. We have the following 0–1 principle:
Let $$C$$ be a circuit with $$\land$$ and $$\lor$$ gates, and $$\phi(u_1,\dots,u_n)$$ a property of values of nodes of $$C$$ expressible as a conjunction of quasi-identities in the language of lattices (i.e., implications of the form $$t_1=s_1\et\dots\et t_k=s_k\to t_0=s_0$$, where $$t_i$$ and $$s_i$$ are terms using $$\land$$, $$\lor$$, and the variables $$u_j$$).
If $$\phi(u_1,\dots,u_n)$$ holds whenever $$C$$ is evaluated in the $$\{0,1\}$$ lattice, then it holds whenever $$C$$ is evaluated in an arbitrary distributive lattice.
This is an immediate consequence of the facts that the $$2$$-element lattice generates the quasivariety of distributive lattices (i.e., every distributive lattice can be embedded in a direct product of $$2$$-element lattices), and that values of nodes of $$C$$ are lattice terms in values of the input variables.
Note that $$t\le s$$ is equivalent to $$t\land s=t$$, hence we can freely use inequalities instead of equalities in the statement above.
Now, if $$C$$ is a comparator network with inputs $$x_1,\dots,x_n,y_1,\dots,y_n$$ and outputs $$z_1,\dots,z_{2n}$$, it automatically computes a permutation of the inputs, hence the property that it correctly merges sorted lists can be expressed by the conjunction of the quasi-identities $$x_1\le x_2\et\dots\et x_{n-1}\le x_n\et y_1\le y_2\et\dots\et y_{n-1}\le y_n\to z_i\le z_{i+1}$$ for $$i=1,\dots,2n-1$$, hence if it works for $$0$$$$1$$ inputs, it also works over arbitrary linearly ordered sets.