Sorting numbers using limited systolic coprocessors (Q579941)

The problem of sorting numbers on a random access machine augmented by systolic coprocessors with a small number of processing elements is discussed. A probabilistic algorithm is presented sorting n given numbers in time 0(n log n/log p(n)) with probability at least \(e^{-16/(3 \log^ 2 n)}\to 1\), assuming that the number p(n) of processing elements satisfies \(n\geq p(n)\geq 9 \log^ 2 n\).