Short answer
Nobody knows. The best lower bound we have for an (oblivious) comparator / sorting-network that outputs the median is Ω(n) comparisons, while the best upper bound that is known is still O(n log n). Whether the two bounds can be closed, i.e. whether Θ(n) comparators are sufficient, has been an open problem for more than thirty years.

Details

1. What is a “median network”?
   A comparator (sorting) network is a fixed, data–independent sequence of comparators ⟨(i1 , j1 ),(i2 , j2 ), …⟩; each comparator exchanges the values on wires ik , jk so that the smaller value comes out on ik and the larger on jk . A median (or selection) network with n inputs has to guarantee that after the last comparator the value on a designated wire m is the ⌈n/2⌉-th smallest of the inputs. Nothing else is required to be ordered.

2. Lower bounds
   • Comparison-tree arguments.
   The decision tree for median selection must have at least ( n ⌈n/2⌉ ) ≈ 2n / √(πn) leaves (all permutations in which a given item is the median), so any adaptive comparison algorithm needs
   log2 ( n ⌈n/2⌉ ) = n – Θ(log n)
   comparisons in the worst case. Thus Ω(n) comparisons are necessary.
   • Obliviousness does not change this lower bound: every comparator network must, in particular, touch every input at least once, so Ω(n) is universal.

No super-linear lower bound (e.g. Ω(n log n)) is known; proving such a bound would separate adaptive from oblivious selection and would be a major breakthrough.

3. Upper bounds
   • Trivial O(n log n): sort with an AKS or bitonic network and read the middle wire.
   • O(n log n) is still the best size that has been achieved deterministically for median (or more generally k-th order statistic) with an oblivious network. Ajtai, Komlós and Szemerédi’s AKS construction can be modified to output only the median, but its size stays Θ(n log n).
   • A few papers give depth O(log n) with size Θ(n log n) (e.g. Dowd–Perl 1982; Paterson 1990; Goodrich 2014 for partitioning), but nobody has pushed the size below the logarithmic factor.

4. Randomised / non-comparison models
   With randomisation, hash networks, or the “select the larger of two” primitive you mention, linear size is easy, but these are adaptive in one way or another and therefore do not answer the network question.

5. Previous work on “selection networks”
   Key references:

• J. Dowd and Y. Perl, “Partitioning, k-selection and sorting networks”,
Information Processing Letters 14(1), 1982.
• M. Paterson, “Improved sorting networks with O(log N) depth”,
Algorithmica 5, 1990 (contains a section on selection).
• M. Goodrich, “Deterministic selection and partitioning in regular networks”,
J. Parallel & Distributed Comput. 74(2), 2014.

All of them obtain depth O(log n) and size Θ(n log n).

6. Status
   • Lower bound: Ω(n) (trivial / information-theoretic).
   • Upper bound: O(n log n).
   • Gap: Θ(log n) factor, still open; no indication which way the truth lies.

So at present we do not know whether one can build a linear-size comparator network that always outputs the median; proving either possibility would solve a long-standing open problem in the theory of comparison networks.