Probabilistic parallel algorithms for sorting and selection.

*(English)*Zbl 0578.68040Probabilistic parallel algorithms are presented for the sorting and selection problem in two computational models, decision trees and parallel random access machines. The algorithms are described for a degree of parallelism, that is the number p of processors available, equal to the size of the input, the number n of keys that have to be sorted. They achieve an optimal speed-up of order p compared to the sequential time complexity of these problems. A parallel decision tree in one step may perform up to p comparisons of pairs of keys simultaneously and then branch according to the outcome of these comparisons. The probabilistic version in addition may choose at random which set of pairs to compare in the next step.

Based on a probabilistic sequential algorithm of Floyd and Rivest for the selection problem the first result is a probabilistic parallel algorithm that for any k and any sequence of n keys selects the k-largest and terminates in \(c_ 1\) steps with probability \(1-\exp (\)- n\({}^{\alpha_ 1})\). Here \(c_ i\) and \(\alpha_ i\) are constants independent of n and k. Using this algorithm for \(k=n/2\) to find the median the sorting problem is then solved recursively by partitioning the keys into a smaller and a larger half. It is shown that termination within \(c_ 2 \log n\) steps can be guaranteed with probability 1-exp(- (log n)\({}^{\alpha_ 2})\). The last algorithm achieves similar time and probability bounds for the sorting problem on the parallel random access machine model. Here processors communicate by a common memory with concurrent read, but exclusive write abilites. Processors can independently choose a random bit. In the time analysis the total number of operations and overhead is included. The ingredients of the algorithms are sorting by computing the rank of the keys, random partions of the keys into clusters and fast parallel computation of sums by certain coding techniques.

For the sorting problem, M. Ajtai, J. Komlós and E. Szemerédy [Combinatorica 3, 1-19 (1983; Zbl 0523.68048)], have shown a related result in the sorting network model. Their algorithm has deterministic parallel time complexity c log n for some (large) constant c.

Based on a probabilistic sequential algorithm of Floyd and Rivest for the selection problem the first result is a probabilistic parallel algorithm that for any k and any sequence of n keys selects the k-largest and terminates in \(c_ 1\) steps with probability \(1-\exp (\)- n\({}^{\alpha_ 1})\). Here \(c_ i\) and \(\alpha_ i\) are constants independent of n and k. Using this algorithm for \(k=n/2\) to find the median the sorting problem is then solved recursively by partitioning the keys into a smaller and a larger half. It is shown that termination within \(c_ 2 \log n\) steps can be guaranteed with probability 1-exp(- (log n)\({}^{\alpha_ 2})\). The last algorithm achieves similar time and probability bounds for the sorting problem on the parallel random access machine model. Here processors communicate by a common memory with concurrent read, but exclusive write abilites. Processors can independently choose a random bit. In the time analysis the total number of operations and overhead is included. The ingredients of the algorithms are sorting by computing the rank of the keys, random partions of the keys into clusters and fast parallel computation of sums by certain coding techniques.

For the sorting problem, M. Ajtai, J. Komlós and E. Szemerédy [Combinatorica 3, 1-19 (1983; Zbl 0523.68048)], have shown a related result in the sorting network model. Their algorithm has deterministic parallel time complexity c log n for some (large) constant c.

##### MSC:

68Q25 | Analysis of algorithms and problem complexity |

68Q05 | Models of computation (Turing machines, etc.) (MSC2010) |

68P10 | Searching and sorting |