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

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.


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
Full Text: DOI Link