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?


1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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