<p>How do you decide what the "wrong way" is?  </p>

<p>Take the first wrong-way swap gate, and interchange the two wires going out of it (including all their associated gates) so that it's correct. This doesn't change the fundamental circuit. It may introduce more wrong-way swap gates, but they're all later in the circuit.</p>

<p>Now, you can keep doing this until you've gotten rid of all the wrong-way swap gates. At this point, you may have permuted the order of the output wires, but you will have a circuit which always outputs a fixed permutation of the sorted order. But since if you input the numbers in sorted order, the right-way swap gates never change the order, this fixed permutation must be sorted order. </p>

<p>So for any sorting network, there's an equivalent one with the same number of gates and the same depth which has no wrong-way gates.</p>

CC BY-SA 3.0
2014-06-26T17:44:24.407Z
2014-06-26T18:00:15.953Z
2014-06-26T18:00:15.953Z
Peter Shor 
<p>Intuitively it seems like an optimal (either minimum depth or minimum gates) sorting network should never have to compare-swap two numbers the "wrong" way (such that the larger one goes into the smaller-indexed position and vice versa).</p>

<p>Is this true?</p>

<p>If so, how do you prove it?</p>

<sorting><proofs><intuition><sorting-network>
Would an optimal sorting network ever have to swap two numbers the "wrong" way
dspyz
# Would an optimal sorting network ever have to swap two numbers the "wrong" way

(Asked by: username_0 on 2014-06-26)

Intuitively it seems like an optimal (either minimum depth or minimum gates) sorting network should never have to compare-swap two numbers the "wrong" way (such that the larger one goes into the smaller-indexed position and vice versa).

Is this true?

If so, how do you prove it?

**Tags:** sorting, proofs, intuition, sorting-network

---

## 1 answers

### Answer by username_1 on 2014-06-26. Score: 16 | Accepted answer

How do you decide what the "wrong way" is?

Take the first wrong-way swap gate, and interchange the two wires going out of it (including all their associated gates) so that it's correct. This doesn't change the fundamental circuit. It may introduce more wrong-way swap gates, but they're all later in the circuit.

Now, you can keep doing this until you've gotten rid of all the wrong-way swap gates. At this point, you may have permuted the order of the output wires, but you will have a circuit which always outputs a fixed permutation of the sorted order. But since if you input the numbers in sorted order, the right-way swap gates never change the order, this fixed permutation must be sorted order.

So for any sorting network, there's an equivalent one with the same number of gates and the same depth which has no wrong-way gates.


---

