Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 15 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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