A neural sorting network with O(1) time complexity (Q2365819)

Neural network models have been shown to be able to find ``good'' solutions for some optimization problems in a short time. But, it can not guarantee to find the real optimal solution except by technique similar to simulated annealing. Under such circumstance, we have no systematic way to determine the annealing schedule and have no easy way to predict the time needed for convergence. The basic operation of each neuron is the summation of weighted inputs, which takes \(O(1)\) time. That is, it can sum any number of real values in constant time. We show that sorting can be accomplished using only such operations. We present a neural network architecture to solve the sorting problem. A multi-layer feed forward neural network is proposed to solve sorting problems. The network has \(O(n^ 3)\) neurons and \(O(n^ 3)\) links. No matter what the input size is, the number of layers is fixed. Thus, the computation time of the network is independent of input size, and the sorting network has time complexity of \(O(1)\).