Optimal Parallel Sorting Scheme by Order Statistics
Mark C. K. Yang, Jun Steed Huang, Yuan-Chieh Chow · SIAM Journal on Computing · 1987
This paper presents a detailed analysis of a sampling approach used in the partitioning of a data file for the parallel balanced tree sort in a local area network or a multiprocessor environment. The average overall time complexity for sorting N data on a k processor system is derived. The performance of the parallel sorting rests upon how evenly the file can be partitioned into k ordered subfiles. A data partition scheme by sampling is proposed and analyzed. Formulas for computing the optimal sampling size are obtained. The results also show the computational improvement of the sorting as a function of k and the sampling overhead. The performance of the sampling method is studied and found to be approaching the absolute optimal in some cases.