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

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2014-12-11T06:29:47.013Z
Equivalently, you are asking what is the comparator circuit complexity of (Boolean) majority.
Yuval Filmus
CC BY-SA 3.0
2014-12-11T09:19:43.020Z
@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.
domotorp
CC BY-SA 3.0
2014-12-11T09:21:56.843Z
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.
Yuval Filmus
<ds.algorithms><sorting><sorting-network><selection>
Is it possible to find the median with a linear size sorting network?
domotorp
# Is it possible to find the median with a linear size sorting network?

(Asked by: username_0 on 2014-12-09)

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.

**Tags:** ds.algorithms, sorting, sorting-network, selection

> **Comments:**
> **username_1**: Equivalently, you are asking what is the comparator circuit complexity of (Boolean) majority.  
> **username_0**: @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.  
> **username_1**: 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.  

---

## 0 answers

