Adaptive Bitonic Sorting: An Optimal Parallel Algorithm for Shared-Memory Machines

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 = O(Nlog N), for any computation time T in the range Ω (log ² N) T O(Nlog N). Adaptive bitonic sorting also has a small constant factor, since it performs less than 2Nlog N comparisons, and only a handful of operations per comparison.