1983 · 671 citations · 6 references
ComputingComputer ScienceMathematicsAlgorithmsCombinatoricsData StructuresParallel SortingSorting AlgorithmsSorting ProblemsComplexity Of SortingParallel Sorting NetworksSortingSorting NetworksSorting Systems
The purpose of this paper is to describe a sorting network of size 0(n log n) and depth 0(log n).
6
Sorting networks and their applications
Kenneth E. Batcher · 1968 · 2.4K citations
Space bounds for a game on graphs
Wolfgang J. Paul, Robert E. Tarjan, James R. Celoni · Theory of Computing Systems · 1976 · 127 citations
On non-linear lower bounds in computational complexity
Leslie G. Valiant · 1975 · 68 citations · Full text
A note on a construction of Margulis
Dana Angluin · Information Processing Letters · 1979 · 15 citations