Abstract
We give a sorting network with $cn n$ comparisons. The algorithm can be performed in $c n$ parallel steps as well, where in a parallel step we compare $n/2$ disjoint pairs. In the $i$th step of the algorithm we compare the contents of registers $Rj(i)$, and $Rk(i)$, where $j(i)$, $k(i)$ are absolute constants then change their contents or not according to the result of the comparison.
