Parallelized QuickSort with Optimal Speedup

Abstract

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.