An Optimal Parallel Sort Algorithm for Minimum Data Movement


The Transactions of the Korea Information Processing Society (1994 ~ 2000), Vol. 1, No. 3, pp. 290-298, Sep. 1994
10.3745/KIPSTE.1994.1.3.290,   PDF Download:

Abstract

In this paper we propose parallel sorting algorithm, taking 0(n^x log n)time complexity, 0(n^x log n) cost(parallel running time * number of peocessors) and 0(n^1-x n^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.


Statistics
Show / Hide Statistics

Statistics (Cumulative Counts from September 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article
[IEEE Style]
H. S. Soo and S. J. Hong, "An Optimal Parallel Sort Algorithm for Minimum Data Movement," The Transactions of the Korea Information Processing Society (1994 ~ 2000), vol. 1, no. 3, pp. 290-298, 1994. DOI: 10.3745/KIPSTE.1994.1.3.290.

[ACM Style]
Hong Sung Soo and Sim Jae Hong. 1994. An Optimal Parallel Sort Algorithm for Minimum Data Movement. The Transactions of the Korea Information Processing Society (1994 ~ 2000), 1, 3, (1994), 290-298. DOI: 10.3745/KIPSTE.1994.1.3.290.