An Optimal Parallel Sort Algorithm for Minimum Data Movement
Seong-Su Hong, Jae-Hong Sim · The Transactions of the Korea Information Processing Society · 1994
In this paper we propose parallel sorting algorithm, taking 0( log n) time complexity, 0( log n) cost (parallel running time * number of processors) and 0( x＋ )data movement complexity under the ERWW- PRAM model. The methods for solving these problems similar. Parallel algorithm finds pivot for partitioning the data into ordered subsets of approximately equal size by using encording pointers..