Bitonic Sort on a Mesh-Connected Parallel Computer
- 1 January 1979
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-28 (1), 2-7
- https://doi.org/10.1109/tc.1979.1675216
Abstract
An O(n) algorithm to sort n2elements on an Illiac IV-like n × n mesh-connected processor array is presented. This algorithm sorts the n2elements into row-major order and is an adaptation of Batcher's bitonic sort. A slight modification of our algorithm yields an O(n) algorithm to sort n2elements into snake-like row-major order. Extensions to the case of a j-dimensional processor array are discussed.Keywords
This publication has 5 references indexed in Scilit:
- Some Complexity Results for Matrix Computations on Parallel ProcessorsJournal of the ACM, 1978
- Sorting on a mesh-connected parallel computerCommunications of the ACM, 1977
- Parallel Processing with the Perfect ShuffleIEEE Transactions on Computers, 1971
- The ILLIAC IV ComputerIEEE Transactions on Computers, 1968
- Very high-speed computing systemsProceedings of the IEEE, 1966