Expected sorting time of random permutation using random comparators

Question

In sorting networks, a comparator of positions $i < j$ is an operator which takes a permutation, checks if $p_i > p_j$, and if it is the case, swaps $p_i$ and $p_j$.

Using this, we can define the following procedure:

1. Uniformly choose a permutation $p$ of $1, 2, ..., n$
2. Until $p$ is sorted (i.e. it's the identity permutation):
   • Uniformly choose two indices, $i < j$, and apply the comparator $i, j$ to $p$.

There are two random variables which interest us: $X$, the number of iterations of the loop until the permutation is sorted, and $Y$, the number of swaps performed. In particular, we are interested in their expected value.

Simulating this procedure many times for multiple values of $n$ seems to suggest that $\mathbf{E}[X] = \Theta(n^2 \log(n))$, while $\mathbf{E}[Y] = \omega(n \log(n))$, and perhaps $\mathbf{E}[Y] = \Theta(n \log(n) \log(\log(n)))$, although it's more vague.

Is this correct? If it is, is there a nice value to $\lim_{n\to \infty} \frac{\mathbf{E}[X]}{n^2 \log(n)}$ and $\lim_{n\to \infty} \frac{\mathbf{E}[Y]}{n \log(n) \log(\log(n))}$? If not, what are the correct asymptotic expressions?

EDIT: I believe can prove that $\mathbf{E}[X] = O(n^3)$ for any distribution of permutations, since the time to sort a permutation of size $n$ is at most the time to bring $n$ to the $n$-th place (from which it can't be displaced), which is expected $\binom{n}2$, plus the time to sort the rest of the permutation. So we get $\binom{n}{2} + \binom{n-1}{2} + \cdots = \Theta(n^3)$. However, this still seems much more than the actual value.

Answer 1

$\DeclareMathOperator\E{E}$I will show the upper bound $\E[X]=O(n^2\log n)$. Let $D(m)$ denote the number of inversions in a random permutations after applying $m$ random comparators.

It is easy to see that if $\pi$ is a permutation with $d$ inversions, and we apply a random comparator $(i,j)$ to $\pi$, then either nothing changes (if $(i,j)$ is not itself an inversion of $\pi$), or the number of inversions strictly decreases (if $(i,j)$ is an inversion, which happens with probability $d\binom n2^{-1}$). Thus, $\E[D(m+1)\mid D(m)=d]\le d-d\binom n2^{-1}$, that is,

$$\E[D(m+1)]\le\left(1-\tbinom n2^{-1}\right)\E[D(m)].$$

It follows that

$$\begin{align*} \Pr[X\ge m+1]&=\Pr[D(m)\ge1]\le\E[D(m)]\\&\le\tbinom n2\left(1-\tbinom n2^{-1}\right)^m\le\exp\left(2\log n-\tfrac{2m}{n^2}\right), \end{align*}$$

which implies

$$\begin{align*} \E[X]&\le n^2\log n+\sum_{s=1}^\infty\Pr[X\ge n^2\log n+s]\\&\le n^2\log n+\sum_{s=0}^\infty e^{-2s/n^2}=n^2\log n+O(n^2). \end{align*}$$

Answer 2

Here's a proof that $\mathbf{E}[X] = O(n^2 \log^2(n))$. Let's assume WLOG $n$ is a power of 2. Let's calculated the expected time until all values bigger than $\frac{n}2$ are in the second half (and all the ones smaller or equal are in the first one). Let's denote by $Z$ the number of values bigger than $\frac{n}2$ in the first half. Note that each performed swap either keeps $Z$ the same, or decreases it by 1.

Additionally, the number of swaps which decrease it by $1$ (interesting swaps) is $Z^2$, since you need to select one of the $Z$ numbers bigger than $\frac{n}2$ in the first half, and one of the $Z$ numbers smaller than $\frac{n}2$ in the second half.

Therefore, for a given value of $Z$, the expected time until it decreases it $\frac{n^2}{Z^2}$. The total expected time, until $Z$ reaches 0, is $\sum_{i=1}^{Z_\text{start}}\frac{n^2}{i^2} < n^2 \sum_{i=1}^\infty \frac1{i^2} = O(n^2)$.

After this happens, we will do the same for each of the two halves, with $\frac{n}4$ and $\frac{3n}4$. We will have $Z_0$ for the first half and $Z_1$ for the second half. This time we will write $Z = Z_0 + Z_1$. The number of interesting swaps is $Z_0^2 + Z_1^2 \geq Z_0 + Z_1 = Z$. Therefore, the expected time until this second layer is sorted is at most $\sum_{i=1}^{Z_\text{start}}{\frac{n^2}i} = n^2 H_{Z_\text{start}}$.

We can continue to do this for all $\log(n)$ layers, and since $Z \leq N$ at any time for any level, we get that in total $\mathbf{E}[X] = O(n^2 \log^2(n))$.