The Siftsort algorithm

A description is given of Siftsort, a highly parallel algorithm, which takes O(log²₂ n) steps to sort n items of data on fewer than n log₂ 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