Adaptive bitonic sorting: An optimal parallel algorithm for shared-memory machines. (English) Zbl 0677.68070

Bilardi, Gianfranco; Nicolau, Alexandru

SIAM J. Comput. 18, No. 2, 216-228 (1989).

Summary: A parallel algorithm, called adaptive bitonic sorting, that runs on a PRAC (parallel random access computer), a shared-memory multiprocessor where fetch and store conflicts are disallowed, is proposed. On a P processors PRAC, the algorithm presented here achieves optimal performance \(TP=0(N \log N)\), for any computation time T in the range \(\Omega (\log^ 2N)\leq T\leq 0(N \log N)\). Adaptive bitonic sorting also has a small constant factor, since it performs less than 2N log N comparisons, and only a handful of operations per comparison.

MSC:

68P10	Searching and sorting
68N25	Theory of operating systems
68Q25	Analysis of algorithms and problem complexity
68W99	Algorithms in computer science
68N99	Theory of software

Keywords:

parallel computation; shared-memory machines; bitonic sequence; time \(\times \) processors optimality; sorting