# Sort numbers using only 2 hidden layers

I'm reading the cornerstone paper Sequence to Sequence Learning with Neural Networks by Ilya Sutskever and Quoc Le. On the first page, it briefly mentions that:

A surprising example of the power of DNNs is their ability to sort
N N-bit numbers using only 2 hidden layers of quadratic size


Can anyone briefly outline how to sort numbers using only 2 hidden layers?

## 2 Answers

Doing some research, I found a paper which proves that sorting can be done with at most 3 layers, and that their solution is optimal if you restrict the size of the network to be polynomial w.r.t. to the number of input numbers:

Depth Efficient Neural Networks for Division and Related Problems, see Theorem 7 on page 955 (page 10 in the PDF).

• Thanks for finding the relevant paper! Actually, this paper does the sorting with "depth" 3, which appears to mean just two hidden layers. See also their reference 14 which they rely on for the lower bound, "Threshold Circuits of Bounded Depth" igi-web.tugraz.at/people/maass/psfiles/34o.pdf (also on ResearchGate) esp pages 131-132 (3-4 in pdf). – Ben Reiniger Jul 13 '19 at 12:41

I'd imagine one could come up with weights manually to do the job exactly, but maybe the point is to be able to train one? A couple of examples:

How to sort numbers using Convolutional Neural Network?

https://github.com/primaryobjects/nnsorting