An 0(n log n) sorting network

1983/01/01 by Miklós Ajtai, János Komlós, Endre Szemerédi · 9 citations
Computer Science · #Algorithms and Data Compression #Cellular Automata and Applications #Interconnection Networks and Systems

paper · doi:10.1145/800061.808726

openalex publication_date 1983/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29

Abstract

The purpose of this paper is to describe a sorting network of size 0(n log n) and depth 0(log n).

Cited by

• Randomized speed-ups in parallel computation
• A new upper bound for Shellsort
• Short monotone formulae for the majority function
• Qubit Routing for (Almost) Free
• Parallel Algorithmic Techniques For CombinationalComputation
• Distributed computing column
• Resource Oblivious Sorting on Multicores
• Expander graph [wikipedia]
• Sorting algorithm [wikipedia]