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
Conference_Titel :
Databases, Parallel Architectures and Their Applications,. PARBASE-90, International Conference on