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.
Is it possible to find the median with a linear size sorting network?
ds.algorithms;sorting;sorting network;selection