%0 Conference Paper %1 ajtai83 %A Ajtai, Miklós %A Komlós, János %A Szemerédi, Endre %B Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing %C New York, NY, USA %D 1983 %I ACM %K aks algorithm classic expander galactic graph.theory halver ramanujan sorting sorting.network %P 1--9 %R 10.1145/800061.808726 %T An $O(n n)$ Sorting Network %X The purpose of this paper is to describe a sorting network of size $O(n n)$ and depth $O(n)$. A natural way of sorting is through consecutive halvings: determine the upper and lower halves of the set, proceed similarly within the halves, and so on. Unfortunately, while one can halve a set using only $O(n)$ comparisons, this cannot be done in less than log $n$ (parallel) time, and it is known that a halving network needs $1/2 n n$ comparisons. It is possible, however, to construct a network of $O(n)$ comparisons which halves in constant time with high accuracy. This procedure ($\epsilon$-halving) and a derived procedure ($\epsilon$-nearsort) are described below, and our sorting network will be centered around these elementary steps. %@ 0-89791-099-0

@inproceedings{ajtai83, abstract = {The purpose of this paper is to describe a sorting network of size $O(n \log n)$ and depth $O(\log n)$. A natural way of sorting is through consecutive halvings: determine the upper and lower halves of the set, proceed similarly within the halves, and so on. Unfortunately, while one can halve a set using only $O(n)$ comparisons, this cannot be done in less than log $n$ (parallel) time, and it is known that a halving network needs $1/2 n \log n$ comparisons. It is possible, however, to construct a network of $O(n)$ comparisons which halves in constant time with high accuracy. This procedure ($\epsilon$-halving) and a derived procedure ($\epsilon$-nearsort) are described below, and our sorting network will be centered around these elementary steps.}, acmid = {808726}, added-at = {2014-04-19T23:56:12.000+0200}, address = {New York, NY, USA}, author = {Ajtai, Mikl\'{o}s and Koml\'{o}s, J\'{a}nos and Szemer{\'e}di, Endre}, biburl = {https://www.bibsonomy.org/bibtex/293cdfa043dfc77103f799a6ec937f3cd/ytyoun}, booktitle = {Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing}, doi = {10.1145/800061.808726}, interhash = {b13f501402061d8e2c152749a1a29854}, intrahash = {93cdfa043dfc77103f799a6ec937f3cd}, isbn = {0-89791-099-0}, keywords = {aks algorithm classic expander galactic graph.theory halver ramanujan sorting sorting.network}, numpages = {9}, pages = {1--9}, publisher = {ACM}, series = {STOC '83}, timestamp = {2016-11-11T09:14:50.000+0100}, title = {An $O(n \log n)$ Sorting Network}, year = 1983 }