Sorting Networks of Logarithmic Depth, Further Simplified

1. Ajtai, M., Komlós, J., Szemerédi, E.: Sorting in clog n parallel steps. Combinatorica 3(1), 1–19 (1983)

   Article  MATH  MathSciNet  Google Scholar 

2. Ajtai, M., Komlós, J., Szemerédi, E.: An \(\mathcal{O}(n\log n)\) sorting network. In: Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, pp. 1–9. Association for Computing Machinery (1983)

3. Ajtai, M., Komlós, J., Szemerédi, E.: Halvers and expanders. In: Proceedings, 33rd Annual Symposium on Foundations of Computer Science, pp. 686–692. IEEE Computer Society Press (1992)

4. Akl, S.G.: Parallel Computation: Models and Methods. Prentice-Hall, Englewood Cliffs (1997)

   Google Scholar 

5. Alekseev, V.E.: Sorting algorithms with minimum memory. Kibernetika 5(5), 99–103 (September–October, 1969)

   Google Scholar 

6. Batcher, K.E.: Sorting networks and their applications. In: Spring Joint Computer Conference. AFIPS Conference Proceedings, vol. 32, pp. 307–314. Thompson Book Company (1968)

7. Chvátal, V.: Lecture notes on the new AKS sorting network. DCS-TR-294, Computer Science Department, Rutgers University (October, 1992)

8. Cole, R., Ó’Dúnlaing, C.: Note on the AKS sorting network (expository note). Technical Report # 243, Computer Science Department, New York University (1986)

9. Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press, Cambridge (2001)

   MATH  Google Scholar 

10. Gibbons, A., Rytter, W.: Efficient Parallel Algorithms. Cambridge University Press, Cambridge (1988)

    MATH  Google Scholar 

11. Knuth, D.E.: The Art of Computer Programming, vol. 3: Sorting and Searching, 2nd edn. Addison-Wesley, Reading (1998)

    Google Scholar 

12. Manos, H.: Construction of halvers. Inf. Process. Lett. 69(6), 303–307 (1999)

    Article  MATH  MathSciNet  Google Scholar 

13. Parberry, I.: Parallel Complexity Theory. Pitman, London (1987)

    MATH  Google Scholar 

14. Paterson, M.S.: Improved sorting networks with \(\mathcal{O}(\log N)\) depth. Algorithmica 5(1), 75–92 (1990)

    Article  MATH  MathSciNet  Google Scholar 

15. Pippenger, N.: Communication networks. In: van Leeuwen, J. (ed.) Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity, pp. 805–833. Elsevier/MIT Press (1990), Chapter 15

16. Smith, J.R.: The Design and Analysis of Parallel Algorithms. Oxford University Press, Oxford (1993)

    MATH  Google Scholar 

Download references