A Cost Optimal Parallel Quicksorting and Its Implementation on a Shared Memory Parallel Computer

摘要

This paper discusses a parallel quicksort algorithm that is cost optimal, in average, using O(n/log(n)) processors. The cost optimality is mainly due to a cost optimal partitioning algorithm that utilizes all the processors when partitioning the array. A temporary array of the same size as the original array is needed during the partitioning process. The prefix sums are used to determine where a processor can copy its data. We will prove that the algorithm has an average case complexity O(log~2n), where n is the size of the data array. We will also discuss the implementation of our algorithm on a shared memory parallel computer and demonstrate that it outperforms other O(log~2n) parallel sorting algorithms. In addition, it outperforms the sequential quicksort algorithm starting with two processors.