Short answer: This is open.

More detail:

• Model. A “sorting network” here means a fixed (oblivious) comparator network: the sequence of compare–exchange operations does not depend on the input. One can specialize such a network to compute only the median (or, more generally, the k-th order statistic), often called a selection network.

• Upper bounds. The best general deterministic constructions for exact selection in comparator networks have size O(n log k), where k is the number of selected items (so for median, k ≈ n/2 and the bound is O(n log n)). This can be obtained, for example, by using standard sorting networks (Batcher, AKS, or more practical near-AKS constructions) and ignoring all outputs except the middle one, or by dedicated selection/compaction networks from the literature on cardinality/selection constraints. Depth can be O(log n) (e.g., AKS), but the size remains O(n log n).

• Lower bounds. Beyond the trivial Ω(n) bound (you must “touch” each input a constant number of times), no superlinear lower bound is known for computing the exact median (or even majority) with comparator networks. In particular, on 0–1 inputs, median coincides with the majority function, and it is a long-standing open problem whether majority (hence median) admits linear-size comparator circuits. Thus we do not know whether O(n) comparators suffice, and we also do not know any Ω(n log n) lower bound for median/majority in this model.

• References and context.

  • Knuth, The Art of Computer Programming, Vol. 3 (Sorting and Searching), §5.3.4 discusses sorting/selection networks and notes that while O(n log n) upper bounds are known, linear-size networks for exact selection are not known; superlinear lower bounds are also unknown.
  • Work on “selection networks” in the SAT/constraint-programming community (e.g., Asín et al., “Cardinality Networks”; Codish et al., “Sorting networks: To the end and back”) provides practical O(n log k) constructions and surveys, but does not resolve the asymptotic question for k ≈ n/2.
  • Comparator-circuit complexity (class CC) places majority/median squarely within the model and highlights the lack of strong size lower bounds for these functions.

About your remark (max-only comparators):

• Your primitive “given a,b, output one that is ≥ the other” is a max gate. Networks that only propagate the larger of two inputs discard information, making them strictly weaker than full compare–exchange networks. Such “tournament” or “knock-out” style models have been studied in various forms (e.g., for finding maxima, elites, or approximate selection), but exact median with linear worst-case comparisons in a purely max-only oblivious network would be quite unusual; I’m not aware of a standard reference that establishes this exact result. If your proof yields an oblivious construction (fixed wiring independent of data), it would be interesting to write up; if it is adaptive (data-dependent), then it aligns with the classic linear-time selection algorithms but does not translate into a comparator network.

Summary: As of current knowledge, there is no known linear-size comparator (sorting) network that finds the exact median, and no result ruling one out; the problem remains open. The best general bounds are Θ(n log n) size and O(log n) depth.