14
$\begingroup$

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?

$\endgroup$
15
  • 1
    $\begingroup$ 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. $\endgroup$
    – daniello
    Feb 28, 2018 at 21:13
  • 2
    $\begingroup$ 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. $\endgroup$
    – D.W.
    Feb 28, 2018 at 21:42
  • 2
    $\begingroup$ @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). In $s$, that input cannot reach $(x_0, x_2), (x_0, x_1)$. In $s'$ it can. $\endgroup$
    – Neal Young
    Mar 3, 2018 at 23:57
  • 3
    $\begingroup$ 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, 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?) $\endgroup$
    – Neal Young
    Mar 4, 2018 at 3:26
  • 2
    $\begingroup$ 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'$. $\endgroup$
    – Neal Young
    Mar 4, 2018 at 16:23

1 Answer 1

3
$\begingroup$

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 < 200$ taking the mean over $100$ gate sequences with $6400$ bit sequences used to approximate the count: Approximate number of gates 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

$\endgroup$
7
  • 2
    $\begingroup$ 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). $\endgroup$ Mar 5, 2018 at 14:46
  • 1
    $\begingroup$ It looks the same for exact up to $n = 27$, but I don’t view that as conclusive. $\endgroup$ Mar 5, 2018 at 15:28
  • 1
    $\begingroup$ @JoshuaGrochow: I've added exact values up to $n = 80$. $\endgroup$ Mar 6, 2018 at 8:02
  • 1
    $\begingroup$ 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$.) $\endgroup$ Mar 6, 2018 at 17:53
  • 1
    $\begingroup$ 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. :) $\endgroup$ Mar 6, 2018 at 18:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.