DocumentCode :
2884253
Title :
The Siftsort algorithm
Author :
Bentin, J. ; Modi, J.J.
fYear :
1990
fDate :
7-9 Mar 1990
Firstpage :
529
Abstract :
A description is given of Siftsort, a highly parallel algorithm, which takes O(log22 n) steps to sort n items of data on fewer than n log2 n processors. Although a comparison-exchange algorithm, it separates out the comparisons from the exchanges, with an intermediate logical step of selectively annihilating-that is, sifting-an array representing the results of comparisons. The algorithm proceeds by successive sweeps, with each sweep consisting of three stages: comparison, sifting, and exchange. Unlike Batcher´s sort, the method is robust against random errors occurring in the sorting process
Keywords :
parallel algorithms; sorting; Siftsort; comparison; comparison-exchange algorithm; exchange; highly parallel algorithm; Logic arrays; Parallel algorithms; Robustness; Sorting;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Databases, Parallel Architectures and Their Applications,. PARBASE-90, International Conference on
Conference_Location :
Miami Beach, FL
Print_ISBN :
0-8186-2035-8
Type :
conf
DOI :
10.1109/PARBSE.1990.77196
Filename :
77196
Link To Document :
بازگشت