A logarithmic time sort for linear size networks
- 1 January 1987
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 34 (1) , 60-76
- https://doi.org/10.1145/7531.7532
Abstract
A randomized algorithm that sorts on an N node network with constant valence in O (log N ) time is given. More particularly, the algorithm sorts N items on an N -node cube-connected cycles graph, and, for some constant k , for all large enough α , it terminates within kα log N time with probability at least 1 - N - α .Keywords
This publication has 9 references indexed in Scilit:
- Parallel permutation and sorting algorithms and a new generalized connection networkJournal of the ACM, 1982
- The cube-connected cycles: a versatile network for parallel computationCommunications of the ACM, 1981
- Fast probabilistic algorithms for hamiltonian circuits and matchingsJournal of Computer and System Sciences, 1979
- Fast parallel sorting algorithmsCommunications of the ACM, 1978
- New Parallel-Sorting SchemesIEEE Transactions on Computers, 1978
- A Fast Monte-Carlo Test for PrimalitySIAM Journal on Computing, 1977
- A Small Business Computer at WorkThe Computer Journal, 1962
- On the Distribution of the Number of Successes in Independent TrialsThe Annals of Mathematical Statistics, 1956
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of ObservationsThe Annals of Mathematical Statistics, 1952