<p>Here's some empirical data for question 2, based on D.W.'s idea applied to bitonic sort.  For $n$ variables, choose $j - i = 2^k$ with probability proportional to $\lg n - k$, then select $i$ uniformly at random to get a comparator $(i,j)$.  This matches the distribution of comparators in bitonic sort if $n$ is a power of 2, and approximates it otherwise.</p>

<p>For a given infinite sequence of gates pulled from this distribution, we can approximate the number of gates required to get a sorting network by sorting many random bit sequences.  Here's that estimate for $n &lt; 200$ taking the mean over $100$ gate sequences with $6400$ bit sequences used to approximate the count:
<a href="https://i.sstatic.net/NMOjI.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/NMOjI.png" alt="Approximate number of gates"></a> 
It appears to match $\Theta(n \log^2 n)$, the same complexity as bitonic sort.  If so, we don't eat an extra $\log n$ factor due to the coupon collector problem of coming across each gate.</p>

<p>To emphasize: I'm using only $6400$ bit sequences to approximate the expected number of gates, not $2^n$.  The mean required gates does rise with that number: for $n = 199$ if I use $6400$, $64000$, and $
640000$ sequences the estimates are $14270 \pm 1069$, $14353 \pm 1013$, and $14539 \pm 965$.  Thus, it's possible getting the last few sequences increases the asymptotic complexity, though intuitively it feels unlikely.</p>

<p><strong>Edit</strong>: Here's a similar plot up to $n = 80$, but using the exact number of gates (computed via a combination of sampling and Z3).  I've switched from power of two $d = j-i$ to arbitrary $d \in [1,\frac{n}{2}]$ with probability proportional to $\frac{\log n - \log d}{d}$.  $\Theta(n \log^2 n)$ still looks plausible.</p>

<p><a href="https://i.sstatic.net/jR45e.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/jR45e.png" alt="Exact numbers of gates"></a></p>

CC BY-SA 3.0
2018-03-05T14:46:36.463Z
Nice experiment! There's a different way the coupon collector issue could arise here, though: you're only sampling a small fraction of the $2^n$ bit sequences needed to verify correctness on all inputs. It seems we can conclude (scientifically, not mathematically of course) from your experiment that a random network of this type and size sorts a *random* permutation whp. I'd also be curious to see exhaustive $2^n$ testing on such random networks for all $n$ up to which you're willing to go. ($n=20$ shouldn't be too bad, maybe even $n=30$ depending on what language & hardware you're using).
Joshua Grochow
CC BY-SA 3.0
2018-03-05T15:28:11.657Z
It looks the same for exact up to $n = 27$, but I don’t view that as conclusive.
Geoffrey Irving
CC BY-SA 3.0
2018-03-06T08:02:46.080Z
@JoshuaGrochow: I've added exact values up to $n = 80$.
Geoffrey Irving
CC BY-SA 3.0
2018-03-06T17:53:38.133Z
Nice! There does appear to be a growing spread to the exact data though, which perhaps indicates an upper bound with an extra factor of $\log n$? (That is, if the "spread" is growing at a rate of $\log n$.)
Joshua Grochow
CC BY-SA 3.0
2018-03-06T18:14:48.727Z
Yeah, we can't rule out an extra factor.  I'd be surprised if it was $\log n$, though, since up at 80 we have $\lg n \approx 6$ and the constant is suspiciously close to $1$ otherwise.  At this point I think theory has to take over. :)
Geoffrey Irving
CC BY-SA 3.0
2018-03-11T06:57:37.737Z
Given a network it should be possible to polynomialy determine if it is a sorting network without sampling inputs.
Meir Maor
CC BY-SA 3.0
2018-03-11T14:57:39.390Z
Meir: No, see http://larc.unt.edu/ian/pubs/snverify.pdf.
Geoffrey Irving
CC BY-SA 3.0
2018-03-05T06:46:12.520Z
2018-03-06T18:19:22.700Z
2018-03-06T18:19:22.700Z
Geoffrey Irving
<p>Given $n$ inputs $x_0, \ldots, x_{n-1}$, we construct a random sorting network with $m$ gates by iteratively picking two variables $x_i, x_j$ with $i &lt; j$ and adding a comparator gate that swaps them if $x_i &gt; x_j$.</p>

<p><strong>Question 1</strong>: For fixed $n$, how large must $m$ be for the network to correctly sort with probability $&gt; \frac{1}{2}$?</p>

<p>We have at least the lower bound $m = \Omega(n^2 \log n)$ since an input that is correctly sorted except that each consecutive pair is swapped will take $\Theta(n^2 \log n^2)$ time for each pair to be chosen as a comparator.  Is that also the upper bound, possibly with more $\log n$ factors?</p>

<p><strong>Question 2</strong>: Is there a distribution of comparator gates that achieves $m = \tilde{O}(n)$, perhaps by choosing close comparators with higher probability?</p>

CC BY-SA 3.0
2018-02-28T21:13:50.103Z
I guess one can get a $O(n^3log^{O(1)})$ upper bound by looking at one input at a time and then union bounding, but that sounds far from tight.
daniello
CC BY-SA 3.0
2018-02-28T21:42:32.690Z
Idea for Question 2: pick a sorting network of depth $O(\log^2 n)$.  At each step, randomly pick one of the gates of the sorting network, and perform that comparison.  After $\tilde{O}(n)$ steps, all gates in the first layer will have been applied.  After another $\tilde{O}(n)$ steps, all gates in the second layer will have been applied.  If you can show that this is monotonic (inserting extra comparisons in the middle of the sorting network can't hurt), you'll have obtained a solution with $\tilde{O}(n)$ comparators in total on average.  I'm not sure whether monoticity actually holds, though.
D.W.
CC BY-SA 3.0
2018-02-28T23:01:32.163Z
@D.W.: And if that argument works for bitonic sort, you can replace the sorting network with a distribution where the probability $p_k$ of picking a comparator of length $k$ is proportional to $1/\lg k$ for $k$ a power of two and zero otherwise.
Geoffrey Irving
CC BY-SA 3.0
2018-03-01T23:40:53.123Z
Do you require that the network correctly sorts every input of length n? Or is your probability dependent on the way in which you generate a random length-n input?

We can assume all elements are unique and can be mapped to 1...n because if they aren't then the problem is strictly easier. But do you have any other constraint on the input?
Phylliida
CC BY-SA 3.0
2018-03-01T23:47:46.113Z
It has to sort every input, but since it's a sorting network that is equivalent to sorting every bit sequence.
Geoffrey Irving
CC BY-SA 3.0
2018-03-03T23:57:37.967Z
@D.W.: Monotonicity doesn't necessarily hold.  Consider sequences $$\begin{eqnarray*}
s &=&(x_1, x_2), (x_0, x_2), (x_0, x_1);\\
s'&=&(x_1, x_2), \mathbf{(x_0, x_1)}, (x_0, x_2), (x_0, x_1).\end{eqnarray*}$$
Sequence $s$ works; $s'$ doesn't (consider input (1, 0, 0)).  The idea is that $(x_0, x_2), (x_0, x_1)$ sorts any input it receives except $(0, 1, 0)$ (see [here](https://cstheory.stackexchange.com/questions/30652/is-it-enough-to-sort-for-polynomially-many-0-1-sequences-for-a-sorting-network?rq=1)).  In $s$, that input cannot reach $(x_0, x_2), (x_0, x_1)$.  In $s'$ it can.
Neal Young
CC BY-SA 3.0
2018-03-04T03:26:22.253Z
Consider the variant where the network is chosen by picking two _adjacent_ variables $x_i, x_{i+1}$ randomly at each step.  Now monotonicity holds (as adjacent swaps don't create inversions).  Apply @D.W.'s idea to an [odd-even sorting network](https://en.wikipedia.org/wiki/Odd–even_sort), which has $n$ rounds: in odd rounds it compares all adjacent pairs where $i$ is odd, in even rounds it compares all adjacent pairs where $i$ is even.  W.h.p. the random network is correct in $O(n^2\log n)$ comparisons, as it "includes" this network. (Or am I missing something?)
Neal Young
CC BY-SA 3.0
2018-03-04T04:12:03.243Z
@Neal: Seems like that would be provable by tracking the number of inversions if $k$ inversions implies at least $k/n$ adjacent flips.
Geoffrey Irving
CC BY-SA 3.0
2018-03-04T04:28:39.057Z
You can have $\Omega(n^2)$ inversions with just 1 adjacent flip (e.g.: 4,5,6,7,8,1,2,3,4).   But I think it's provable as outlined in my comment: it takes $O(n\log n)$ random adjacent comparisons (w.h.p.) to do all odd (or all even) adjacent comparisons.  So you cover one round of the odd-even network in $O(n\log n)$ comparisons, and you cover all $n$ rounds in $O(n^2\log n)$ comparisons.  Then by monotonicity you are done.  (Or am I missing something?)
Neal Young
CC BY-SA 3.0
2018-03-04T06:07:17.773Z
@NealYoung: Yes, that works.  I don't see the easy proof that monotonicity holds for all adjacent networks (though I expect it exists), but odd-even sort plus extra gates certainly takes only $O(n)$ passes.
Geoffrey Irving
CC BY-SA 3.0
2018-03-04T16:23:17.370Z
Monotonicity of adjacent networks: Given $a, b\in\{0,1\}^n$, for $j\in\{0,1,\ldots,n\}$ define $s_j(a) = \sum_{i=1}^j a_i$.  Say $a\preceq b$ if $s_j(a) \le s_j(b)$ ($\forall j$).  Fix any comparison "$x_i < x_{i+1}$".  Let $a'$ and $b'$ come from $a$ and $b$ by doing that comparison.
**Claim 1.** _$a' \preceq a$ and $b' \preceq b$._
**Claim 2:** _if $a\preceq b$, then $a' \preceq b'$._  
Then show inductively:
if $y$ is the result of comparison sequence $s$ on input $x$,
and $y'$ is the result of super-sequence $s'$ of $s$ on $x$, then $y' \preceq y$.  So if $y$ is sorted, so is $y'$.
Neal Young
CC BY-SA 3.0
2018-03-06T03:44:05.920Z
FWIW I think that monotonicity of the odd-even network holds w.r.t.. arbitrary (even non-adjacent) comparisons, in that adding arbitrary comparisons won't break it.  The correctness of the odd-even network follows from an invariant similar to (but not quite) the following: after $2t$ rounds (of adjacent odd/even comparisons), the $i$th smallest is in  position $\le n + 2i-t$ from the top.  (This invariant is "universal" in the sense that it is independent of the input.) I believe the invariant is maintained even if arbitrary additional comparisons (adjacent or not) are interspersed.
Neal Young
CC BY-SA 3.0
2018-03-06T04:12:42.647Z
@NealYoung: Want to upgrade that to an answer?  I think it fully resolves question 1.
Geoffrey Irving
CC BY-SA 3.0
2018-03-06T13:19:47.893Z
Does it resolve Question 1?  If you choose arbitrary comparisons at random, won't it take $m=\Theta(n^3 \log n)$ comparisons to dominate the odd-even network?  This would be similar to Daniello's suggested bound of $O(n^3\log^{O(1)} n)$. But the right answer is more like $O(n^2\log n)$, probably?
Neal Young
CC BY-SA 3.0
2018-03-06T15:23:03.380Z
@NealYoung: Apologies, you’re right that it’s cubic.  And experiments similar to below do show approximate quadratic behavior (not sure about log factors).
Geoffrey Irving
<sorting-network>
Probability that a random sorting network works
Geoffrey Irving
# Probability that a random sorting network works

(Asked by: username_0 on 2018-02-28)

Given $n$ inputs $x\_0, \ldots, x\_{n-1}$, we construct a random sorting network with $m$ gates by iteratively picking two variables $x\_i, x\_j$ with $i < j$ and adding a comparator gate that swaps them if $x\_i > x\_j$.

**Question 1**: For fixed $n$, how large must $m$ be for the network to correctly sort with probability $> \frac{1}{2}$?

We have at least the lower bound $m = \Omega(n^2 \log n)$ since an input that is correctly sorted except that each consecutive pair is swapped will take $\Theta(n^2 \log n^2)$ time for each pair to be chosen as a comparator. Is that also the upper bound, possibly with more $\log n$ factors?

**Question 2**: Is there a distribution of comparator gates that achieves $m = \tilde{O}(n)$, perhaps by choosing close comparators with higher probability?

**Tags:** sorting-network

> **Comments:**
> **username_1**: I guess one can get a $O(n^3log^{O(1)})$ upper bound by looking at one input at a time and then union bounding, but that sounds far from tight.  
> **username_2**: Idea for Question 2: pick a sorting network of depth $O(\log^2 n)$.  At each step, randomly pick one of the gates of the sorting network, and perform that comparison.  After $\tilde{O}(n)$ steps, all gates in the first layer will have been applied.  After another $\tilde{O}(n)$ steps, all gates in the second layer will have been applied.  If you can show that this is monotonic (inserting extra comparisons in the middle of the sorting network can't hurt), you'll have obtained a solution with $\tilde{O}(n)$ comparators in total on average.  I'm not sure whether monoticity actually holds, though.  
> **username_0**: @username_2: And if that argument works for bitonic sort, you can replace the sorting network with a distribution where the probability $p_k$ of picking a comparator of length $k$ is proportional to $1/\lg k$ for $k$ a power of two and zero otherwise.  
> **username_3**: Do you require that the network correctly sorts every input of length n? Or is your probability dependent on the way in which you generate a random length-n input?  We can assume all elements are unique and can be mapped to 1...n because if they aren't then the problem is strictly easier. But do you have any other constraint on the input?  
> **username_0**: It has to sort every input, but since it's a sorting network that is equivalent to sorting every bit sequence.  
> **username_4**: @username_2: Monotonicity doesn't necessarily hold.  Consider sequences $$\begin{eqnarray*} s &=&(x_1, x_2), (x_0, x_2), (x_0, x_1);\\ s'&=&(x_1, x_2), \mathbf{(x_0, x_1)}, (x_0, x_2), (x_0, x_1).\end{eqnarray*}$$ Sequence $s$ works; $s'$ doesn't (consider input (1, 0, 0)).  The idea is that $(x_0, x_2), (x_0, x_1)$ sorts any input it receives except $(0, 1, 0)$ (see [here](https://cstheory.stackexchange.com/questions/30652/is-it-enough-to-sort-for-polynomially-many-0-1-sequences-for-a-sorting-network?rq=1)).  In $s$, that input cannot reach $(x_0, x_2), (x_0, x_1)$.  In $s'$ it can.  
> **username_4**: Consider the variant where the network is chosen by picking two _adjacent_ variables $x_i, x_{i+1}$ randomly at each step.  Now monotonicity holds (as adjacent swaps don't create inversions).  Apply @username_2's idea to an [odd-even sorting network](https://en.wikipedia.org/wiki/Odd–even_sort), which has $n$ rounds: in odd rounds it compares all adjacent pairs where $i$ is odd, in even rounds it compares all adjacent pairs where $i$ is even.  W.h.p. the random network is correct in $O(n^2\log n)$ comparisons, as it "includes" this network. (Or am I missing something?)  
> **username_0**: @Neal: Seems like that would be provable by tracking the number of inversions if $k$ inversions implies at least $k/n$ adjacent flips.  
> **username_4**: You can have $\Omega(n^2)$ inversions with just 1 adjacent flip (e.g.: 4,5,6,7,8,1,2,3,4).   But I think it's provable as outlined in my comment: it takes $O(n\log n)$ random adjacent comparisons (w.h.p.) to do all odd (or all even) adjacent comparisons.  So you cover one round of the odd-even network in $O(n\log n)$ comparisons, and you cover all $n$ rounds in $O(n^2\log n)$ comparisons.  Then by monotonicity you are done.  (Or am I missing something?)  
> **username_0**: @NealYoung: Yes, that works.  I don't see the easy proof that monotonicity holds for all adjacent networks (though I expect it exists), but odd-even sort plus extra gates certainly takes only $O(n)$ passes.  
> **username_4**: Monotonicity of adjacent networks: Given $a, b\in\{0,1\}^n$, for $j\in\{0,1,\ldots,n\}$ define $s_j(a) = \sum_{i=1}^j a_i$.  Say $a\preceq b$ if $s_j(a) \le s_j(b)$ ($\forall j$).  Fix any comparison "$x_i < x_{i+1}$".  Let $a'$ and $b'$ come from $a$ and $b$ by doing that comparison. **Claim 1.** _$a' \preceq a$ and $b' \preceq b$._ **Claim 2:** _if $a\preceq b$, then $a' \preceq b'$._   Then show inductively: if $y$ is the result of comparison sequence $s$ on input $x$, and $y'$ is the result of super-sequence $s'$ of $s$ on $x$, then $y' \preceq y$.  So if $y$ is sorted, so is $y'$.  
> **username_4**: FWIW I think that monotonicity of the odd-even network holds w.r.t.. arbitrary (even non-adjacent) comparisons, in that adding arbitrary comparisons won't break it.  The correctness of the odd-even network follows from an invariant similar to (but not quite) the following: after $2t$ rounds (of adjacent odd/even comparisons), the $i$th smallest is in  position $\le n + 2i-t$ from the top.  (This invariant is "universal" in the sense that it is independent of the input.) I believe the invariant is maintained even if arbitrary additional comparisons (adjacent or not) are interspersed.  
> **username_0**: @NealYoung: Want to upgrade that to an answer?  I think it fully resolves question 1.  
> **username_4**: Does it resolve Question 1?  If you choose arbitrary comparisons at random, won't it take $m=\Theta(n^3 \log n)$ comparisons to dominate the odd-even network?  This would be similar to Daniello's suggested bound of $O(n^3\log^{O(1)} n)$. But the right answer is more like $O(n^2\log n)$, probably?  
> **username_0**: @NealYoung: Apologies, you’re right that it’s cubic.  And experiments similar to below do show approximate quadratic behavior (not sure about log factors).  

---

## 1 answers

### Answer by username_0 on 2018-03-05. Score: 4

Here's some empirical data for question 2, based on username_2's idea applied to bitonic sort. For $n$ variables, choose $j - i = 2^k$ with probability proportional to $\lg n - k$, then select $i$ uniformly at random to get a comparator $(i,j)$. This matches the distribution of comparators in bitonic sort if $n$ is a power of 2, and approximates it otherwise.

For a given infinite sequence of gates pulled from this distribution, we can approximate the number of gates required to get a sorting network by sorting many random bit sequences. Here's that estimate for $n < 200$ taking the mean over $100$ gate sequences with $6400$ bit sequences used to approximate the count:
[![Approximate number of gates](https://i.sstatic.net/NMOjI.png)](https://i.sstatic.net/NMOjI.png)
It appears to match $\Theta(n \log^2 n)$, the same complexity as bitonic sort. If so, we don't eat an extra $\log n$ factor due to the coupon collector problem of coming across each gate.

To emphasize: I'm using only $6400$ bit sequences to approximate the expected number of gates, not $2^n$. The mean required gates does rise with that number: for $n = 199$ if I use $6400$, $64000$, and $
640000$ sequences the estimates are $14270 \pm 1069$, $14353 \pm 1013$, and $14539 \pm 965$. Thus, it's possible getting the last few sequences increases the asymptotic complexity, though intuitively it feels unlikely.

**Edit**: Here's a similar plot up to $n = 80$, but using the exact number of gates (computed via a combination of sampling and Z3). I've switched from power of two $d = j-i$ to arbitrary $d \in [1,\frac{n}{2}]$ with probability proportional to $\frac{\log n - \log d}{d}$. $\Theta(n \log^2 n)$ still looks plausible.

[![Exact numbers of gates](https://i.sstatic.net/jR45e.png)](https://i.sstatic.net/jR45e.png)

> **Comments:**
> **username_5**: Nice experiment! There's a different way the coupon collector issue could arise here, though: you're only sampling a small fraction of the $2^n$ bit sequences needed to verify correctness on all inputs. It seems we can conclude (scientifically, not mathematically of course) from your experiment that a random network of this type and size sorts a *random* permutation whp. I'd also be curious to see exhaustive $2^n$ testing on such random networks for all $n$ up to which you're willing to go. ($n=20$ shouldn't be too bad, maybe even $n=30$ depending on what language & hardware you're using).  
> **username_0**: It looks the same for exact up to $n = 27$, but I don’t view that as conclusive.  
> **username_0**: @JoshuaGrochow: I've added exact values up to $n = 80$.  
> **username_5**: Nice! There does appear to be a growing spread to the exact data though, which perhaps indicates an upper bound with an extra factor of $\log n$? (That is, if the "spread" is growing at a rate of $\log n$.)  
> **username_0**: Yeah, we can't rule out an extra factor.  I'd be surprised if it was $\log n$, though, since up at 80 we have $\lg n \approx 6$ and the constant is suspiciously close to $1$ otherwise.  At this point I think theory has to take over. :)  
> **username_6**: Given a network it should be possible to polynomialy determine if it is a sorting network without sampling inputs.  
> **username_0**: Meir: No, see http://larc.unt.edu/ian/pubs/snverify.pdf.  

---

