Is there a sorting network that makes only $O(n)$ comparisons and finds the median?

The AKS sorting network sorts with $O(\log n)$ parallel steps, but here I am only interested in the number of comparisons. The median of medians algorithm finds the median with $O(n)$ comparisons, but it cannot be implemented as a sorting network.

Remark. In fact, in a recent work, we needed a version that is less powerful than pairwise comparison and resembles sorting networks. In our model one could input two elements, $a$ and $b$, and the output was either "a" or "b", such that the output is at least as big as the other number. (In case of equality, either one of them, and we are interested in worst case complexity.) In this variant we could prove that there is a solution with $O(n)$ comparisons. Of course I am also interested if anyone knows anything about this model ever being studied.

  • 2
    $\begingroup$ Equivalently, you are asking what is the comparator circuit complexity of (Boolean) majority. $\endgroup$ – Yuval Filmus Dec 11 '14 at 6:29
  • $\begingroup$ @Yuval Your result seems to be the only hit on google for "comparator circuit complexity" and even there I cannot see the definition as the minimum number of gates needed, but I suppose you mean the same thing as I do. $\endgroup$ – domotorp Dec 11 '14 at 9:19
  • 1
    $\begingroup$ Actually the comparator circuit model is a bit different, since you are allowed to repeat inputs and their negations. What you are looking for is a comparator network for majority. $\endgroup$ – Yuval Filmus Dec 11 '14 at 9:21

Your Answer

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

Browse other questions tagged or ask your own question.