The 0-1 principle says that if a sorting network works for all 0-1 sequences, then it works for any set of numbers. Is there an $S\subset \{0,1\}^n$ such that if a network sorts every 0-1 sequence from S, then it sorts every 0-1 sequence and the size of $S$ is polynomial in $n$?
For example, if $S$ consists of all sequences where there are at most $2$ runs (intervals) of 1's, then is there a sorting network N and a sequence that is not ordered by N if all members of $S$ are ordered by N?
Answer: As can be seen from the answer and the comments to it, the answer is that for every unsorted string there is a sorting network that sorts every other string. A simple proof for this is the following. Let the string $s=s_1\ldots s_n$ be such that $s_i=0$ for ever $i<k$ and $s_k=1$. Since $s$ is unsorted, after sorting $s_k$ should be $0$. Compare $k$ with every $i$ for which $s_i=1$. Then compare every pair $(i,j)$ such that $i\ne k$ and $j\ne k$ many times. This leaves the whole string sorted, except possibly for $s_k$, which is unsorted for $s$, and for certain other strings that have more $1$'s than $s$. Now compare $s_k$ for $i=n$ downto $1$ except for the place where $s_k$ should go in $s$. This will sort everything but $s$.
Update: I wonder what happens if we restrict the depth of the network to $O(\log n)$.
