  We consider the classical problem of sorting an input array containing $n$
elements, where each element is described with a $k$-bit comparison-key and a
$w$-bit payload. A long-standing open problem is whether there exist $(k + w)
\cdot o(n \log n)$-sized boolean circuits for sorting. We show that one can
overcome the $n\log n$ barrier when the keys to be sorted are short.
Specifically, we prove that there is a circuit with $(k + w) \cdot O(n k) \cdot
\poly(\log^*n - \log^* (w + k))$ boolean gates capable of sorting any input
array containing $n$ elements, each described with a $k$-bit key and a $w$-bit
payload. Therefore, if the keys to be sorted are short, say, $k < o(\log n)$,
our result is asymptotically better than the classical AKS sorting network
(ignoring $\poly\log^*$ terms); and we also overcome the $n \log n$ barrier in
such cases. Such a result might be surprising initially because it is long
known that comparator-based techniques must incur $\Omega(n \log n)$ comparator
gates even when the keys to be sorted are only $1$-bit long (e.g., see Knuth's
"Art of Programming" textbook). To the best of our knowledge, we are the first
to achieve non-trivial results for sorting circuits using non-comparison-based
techniques. We also show that if the Li-Li network coding conjecture is true,
our upper bound is optimal, barring $\poly\log^*$ terms, for every $k$ as long
as $k = O(\log n)$.
