  A new fast (real time) sorter of binary numbers by one-dimensional cellular
automata is proposed. It sorts a list of n numbers represented by k-bits each
in exactly nk steps. This is only one step more than a lower bound.

Cellular Automata and Lattice Gases;Data Structures and Algorithms