Can the zero-one principle be used to prove the stability of a sorting network

Question

When dealing with sorting networks, we can check the validity of a sorting network with only $2^n$ sequences of $0$ and $1$ (where $n$ is the size of the collection to sort) thanks to the zero-one principle:

The zero-one principle states that, if a sorting network can correctly sort all $2^n$ sequences of zeros and ones, then it is also valid for arbitrary ordered inputs.

I have used this principle to prove that my sorting networks worked. However, I also wanted to check whether some of them were stable or not: in order to do so, I tried to feed pairs of $(0, index)$ and $(1, index)$ to the networks instead of simple $0$ and $1$ and checked whether the indices of elements with the same values were still in the correct order after the sort (of course, the sequences were sorted based only on the first value of the pair). It was sufficient to prove that my sorting networks weren't stable since the algorithm was able to find at least one sequence that wasn't stably sorted per network.

However, even if every sequence was stably sorted, I still wouldn't be sure whether the sorting networks are stable or not without answering this question: can the zero-one principle be used to prove the stability of a sorting network?

Answer 1

You can use a $0/1/2$ principle, in which the inputs are $\{0,1,2\}$, and $1$-inputs are also annotated by their indices. The network should sort the input successfully, maintaining the order of the $1$-entries. This is clearly a necessary condition, and it's not too hard to show that it is sufficient.

That doesn't quite answer your own question, though I conjecture that your criterion isn't sufficient. All one needs to do in order to prove my conjecture is to give a sorting network satisfying your condition but not mine. You can try looking for such a network using a computer. If you can find no such network, perhaps your criterion does work after all.