%0 Journal Article %1 ajtai83 %A Ajtai, Miklós %A Komlós, János %A Szemerédi, Endre %D 1983 %I Springer-Verlag %J Combinatorica %K aks algorithm classic expander galactic halver ramanujan sorting sorting.network %N 1 %P 1--19 %R 10.1007/BF02579338 %T Sorting in $c n$ Parallel Steps %V 3 %X 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.

@article{ajtai83, abstract = {We give a sorting network with $cn \log n$ comparisons. The algorithm can be performed in $c \log 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.}, added-at = {2014-04-20T15:26:05.000+0200}, author = {Ajtai, Mikl\'{o}s and Koml\'{o}s, J\'{a}nos and Szemer{\'e}di, Endre}, biburl = {https://www.bibsonomy.org/bibtex/248acc18110e7b13a4e26b3aecad916bb/ytyoun}, doi = {10.1007/BF02579338}, interhash = {093a660a191de24eead7922ed5565c6d}, intrahash = {48acc18110e7b13a4e26b3aecad916bb}, issn = {0209-9683}, journal = {Combinatorica}, keywords = {aks algorithm classic expander galactic halver ramanujan sorting sorting.network}, language = {English}, number = 1, pages = {1--19}, publisher = {Springer-Verlag}, timestamp = {2016-11-11T09:12:20.000+0100}, title = {Sorting in $c \log n$ Parallel Steps}, volume = 3, year = 1983 }