Circuit complexity of Majority function Let $f: \{0,1\}^n \to \{0,1\}$ be the majority function, i.e. $f(x) = 1$ if and only if $\sum_{i = 1}^n x_i &gt; n/2$. I was wondering if there was a simple proof of the following fact (by "simple" I mean not relying on the probabilistic method like Valiant 84 did or on sorting networks; preferably providing an explicit, straightforward construction of the circuit): 

$f$ can be computed by a family of circuits of $O(\log(n))$ depth, poly(n) size, where the gates consists of NOT gates, 2-input OR gates, and 2-input AND gates.
Computing restricted threshold gate ($\sum_i x_i \geq k$) is essentially sorting input bits.

If you can sort the bits then it is easy to compare the result to $k$ and 
compute restricted threshold.

On the other hand, assume that we have an circuits to compute restricted threshold. 
We can do a parallel search to find the number of ones in the input and 
output the sorted list.

These preserve circuit depth. So if you come up with a new $\mathsf{NC^1}$ circuit to compute the restricted threshold then it will give a depth $O(\lg n)$ sorting circuit.
So if we come up with a simple argument for showing majority is in $\mathsf{NC^1}$ 
you have found a simple depth-$O(\lg n)$ sorting circuit 
(other than the one based on AKS sorting network).

Note that it is easy to implement the restricted threshold using majority by adding new 1 and 0 inputs to the majority gate.



Previously this answer claimed that it can be done using divide and conquer and the fact that binary addition is in $\mathsf{AC^0}$. That only shows that majority is in $\mathsf{AC^1}$ and $\mathsf{NC^2}$ since we have unbounded fan-in gates in the binary addition if we do it directly. However it can be done with a bit more work.

We have to use the trick called three-for-two to remain in depth $O(\lg n)$. 


  three-for-two binary addition:
  given three binary numbers $a,b,c$ we can compute two binary numbers $x,y$ such that
  $a+b+c = x+y$.


Another method is to use signed digit representation of integers where addition can be done in depth $O(1)$ and fan-in 2. (The idea is to use the flexibility that a number can be represented in more than one way to make sure that carries do not propagate).

See section 4 and exercise 4 in


David Mix Barrington and Alexis Maciel, "Advanced Course on Computational Complexity", lecture 6, IAS/PCMI, 2000.