A low-cost neural sorting network with O(1) time complexity

In this paper, we present an O(1) time neural network with O(n(1+ε)) neurons and links to sort n data, ε > O. For large-size problems, it is desirable to have low-cost hardware solutions. In order to solve the sorting problem in constant time and with less hardware-cost, we adopt Leighton's column sort [5] as the main architecture. Then we use Chen and Hsieh's neural network [3] with O(n³) complexity as the lowest-level sub-networks. By using recursive techniques properly, we are able to explore constant-time, low-complexity neural sorting networks.