K-way bitonic sort
- 1 February 1989
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. 38 (2) , 283-288
- https://doi.org/10.1109/12.16506
Abstract
The k-way bitonic sort algorithm, a generalization of K.E. Batcher's bitonic sort algorithm (1968), is presented. This variation of the algorithm is based on a k-way decomposition instead of a two-way decomposition. It is proven that Batcher's bitonic sequence decomposition theorem still holds with this multiway decomposition. This leads to applications of sorting networks with bitonic sorters of arbitrary or mixed sizes.Keywords
This publication has 18 references indexed in Scilit:
- Parallel Sorting with Serial MemoriesIEEE Transactions on Computers, 1985
- The complexity of sorting on distributed systemsInformation and Control, 1984
- Efficient VLSI Networks for Parallel Processing Based on Orthogonal TreesIEEE Transactions on Computers, 1983
- The cube-connected cycles: a versatile network for parallel computationCommunications of the ACM, 1981
- On the Complexity of Sorting in Magnetic Bubble Memory SystemsIEEE Transactions on Computers, 1980
- Bitonic Sort on a Mesh-Connected Parallel ComputerIEEE Transactions on Computers, 1979
- Sorting on STARIEEE Transactions on Software Engineering, 1978
- Implementation of Permutation Functions in Illiac IV-Type ComputersIEEE Transactions on Computers, 1976
- Access and Alignment of Data in an Array ProcessorIEEE Transactions on Computers, 1975
- Parallel Processing with the Perfect ShuffleIEEE Transactions on Computers, 1971