SIAM Journal on Computing · 1975 · 13 citations · 1 references
ComputingComputer ScienceAlgorithmsCombinatoricsData StructuresParallel SortingSorting AlgorithmsSorting ProblemsComparison ComplexityMerge SortParallel Sorting NetworksSortingSorting Networks
This paper develops sorting networks using the divide/sort/merge strategy. These networks require \[ (0.25)N( \log _2 N )^2 - (0.386)N( \log _2 N ) + O(N) \] comparison-interchanges to sort a list of length N. This is an improvement of order $N(\log _2 N)$ over the best networks previously reported. (Using different methods, Van Voorhis [8] has improved upon these results.)
1
Lester R. Ford, Selmer Martin Johnson · American Mathematical Monthly · 1959 · 51 citations