To determine if a sorting network with ( O(n) ) comparisons can find the median, we first clarify the definition of a sorting network: a fixed sequence of comparators (each comparing and swapping two elements if out of order) that sorts any input array. The goal is to check if such a network can exist with linear comparison count while outputting the median.

Key Observations:

1. **Sorting N...

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

No “linear‐size” oblivious median‐finding network is known, and nobody has proved one impossible beyond the trivial Ω(n) bound. In fact all of the classic “sorting‐network” constructions (Batcher’s bitonic or odd–even networks, AKS, etc.) use Θ(n log n) comparators, and the obvious way to get the median is to sort and then read off the middle wire. On the lower‐bound side the only general fact i...

Short answer
Nobody knows. The best upper bound that is known for an oblivious comparator (sorting) network which outputs only the median of n keys is Θ(n log n) comparators – we can always sort and take the middle element – and the best lower bound that is known is the obvious Ω(n). No super-linear lower bound and no o(n log n) construction is known. In particular, it is an open problem ...

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.

-----------------------------------------------...

Excellent question that touches on a fundamental and often misunderstood topic in the theory of computation: the distinction between adaptive algorithms and non-adaptive networks.

Short Answer

No, it is not possible to find the median with a sorting network of linear size. The size of any sorting network that correctly finds the median of n elements (a selection network) is Ω(n log n)....

Finding the Median with a Linear-Size Sorting Network

Based on established computational complexity theory, I believe it's not possible to find the median with a sorting network using only O(n) comparisons.

Why This Is Likely Impossible

Sorting networks are non-adaptive by definition - the sequence of comparisons is fixed in advance and cannot change based on the outcomes of previous c...

First, recall that a sorting network is a fixed sequence of comparisons that is data-independent. The network consists of comparators (which compare two elements and swap them if necessary) arranged in a way that for any input, the network sorts the entire sequen...

This is an excellent question about the fundamental limits of sorting networks for selection problems.

Answer

No, it is not possible to find the median with a linear-size sorting network. This was proven by Alekseev in 1982.

The Impossibility Result

Alekseev proved that any sorting network that finds the median of n elements must use at least Ω(n log n) comparisons. This is a signif...