Does the 0-1 principle apply to merge networks?

Question

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)

Answer 1

$\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.