A Cost Optimal Parallel Quicksort On CREW PRAM

摘要

In this paper we introduce a cost optimal parallel quicksort algorithm. It sorts an array of n elements in O(log~2 n) time using O(n/(log n)) processors on a CREW PRAM. That is, the total cost is O(n log n), the same as an average sequential quicksort algorithm. The key feature of the proposed algorithm is that it partitions the array concurrently. This removes the performance bottleneck proposed by other researchers. Without increasing the complexity, we use an Θ(log n) algorithm to find the mean of the unsorted array and use it as the pivot to ensure that the partitioning process divides the array into two relatively equal size halves. The proposed quicksort algorithm has an average complexity of O(log~2 n).