Parallel sorting and data partitioning by sampling
Jun Steed Huang, Yuan-Chieh Chow · OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) · 1983
A parallel sorting method which requires data partitioning is presented. The ability to partition the data into equal-size ordered subsets is essential in the sorting process. A data partitioning method by sampling is proposed. The complexity and the performance of the sorting and partitioning algorithm are analyzed. Storage bounds and the choice of parameters which determine the sampling size are also discussed. The analysis is developed for parallel sorting in a local network environment, with distributed data sets in secondary storage devices. 9 references.