DocumentCode
2428784
Title
A parallel exchange sort algorithm
Author
Shirazi, Behrooz ; Song, Young-Deok
Author_Institution
Dept. of Comput. Sci. & Eng., Southern Methodist Univ., Dallas, TX, USA
fYear
1989
fDate
22-24 March 1989
Firstpage
366
Lastpage
370
Abstract
A parallel sorting algorithm is introduced which is based on the odd-even transposition (or exchange) sorting scheme. Compared to the parallel sorters of its class, the proposed algorithm requires about the same time complexity but reduces the number of processing elements in half. Using the VLSI measure of area*time/sup 2/, it is shown that this algorithm can outperform comparable parallel exchange sort algorithms. Due to its simple cell design and regular interconnections, the proposed sorter is highly suitable for VLSI implementation.<>
Keywords
computational complexity; parallel algorithms; sorting; VLSI measure; cell design; odd-even transposition; parallel exchange sort algorithm; processing elements; regular interconnections; time complexity; Algorithm design and analysis; Area measurement; Bandwidth; Communication system control; Computer architecture; Computer science; Concurrent computing; Hardware; Logic; Sorting;
fLanguage
English
Publisher
ieee
Conference_Titel
Computers and Communications, 1989. Conference Proceedings., Eighth Annual International Phoenix Conference on
Conference_Location
Scottsdale, AZ, USA
Print_ISBN
0-8186-1918-x
Type
conf
DOI
10.1109/PCCC.1989.37416
Filename
37416
Link To Document