Parallelized QuickSort with Optimal Speedup
David M W Powers · 1990
This paper introduces a parallel sorting algorithm based on QuickSort and having an n-input, n- processor, time complexity of O(log n) exhibited using a CRCW PRAM model. Although existing algorithms of similar complexity are known, this approach leads to a family of algorithms with a considerably lower constant. It is also significant in its close relationship to a standard sequential algorithm.