Probability that a random sorting network works 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$.

Question 1: For fixed $n$, how large must $m$ be for the network to correctly sort with probability $&gt; \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?
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.

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:
 
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.