14
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ Equivalently, you are asking what is the comparator circuit complexity of (Boolean) majority. $\endgroup$
    – Yuval Filmus
    Dec 11, 2014 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, 2014 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, 2014 at 9:21

0

Reset to default

Your Answer

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