article · IEEE Transactions on Computers · 1991

Time-space optimal parallel merging and sorting

Cited by 2Abstract and details only

Abstract

The authors present a parallel merging algorithm that, on an exclusive-read exclusive-write (EREW) parallel random-access machine (PRAM) with k processors merges two sorted lists of total length n in O(n/k+log n) time and constant extra space per processor, and hence is time-space optimal for any value of k<or=n/(log n). The authors also describe how this gives rise to a stable version of the parallel merging algorithm that is similarly time-space optimal on an EREW PRAM. The authors observe that this technique for achieving stability incurs two penalties: a slightly more complicated algorithm and somewhat larger constants of proportionality. These two parallel merges naturally lead to time-space optimal parallel sorting algorithms. Extensions to sorting and open topics for future research are discussed.<<ETX>>

Cite this paper

APA 7

Guan, X., & Langston, M. A. (1991). Time-space optimal parallel merging and sorting. IEEE Transactions on Computers, 40(5), 596–602. https://doi.org/10.1109/12.88483

MLA 9

Guan, Xiaojun, and Michael A. Langston. “Time-space optimal parallel merging and sorting.” IEEE Transactions on Computers, vol. 40, no. 5, 1991, pp. 596–602, https://doi.org/10.1109/12.88483.

Chicago

Guan, Xiaojun, and Michael A. Langston. 1991. “Time-space optimal parallel merging and sorting.” IEEE Transactions on Computers 40 (5): 596–602. https://doi.org/10.1109/12.88483.

Harvard

Guan, X. and Langston, M.A. (1991) ‘Time-space optimal parallel merging and sorting’, IEEE Transactions on Computers, 40(5), pp. 596–602. Available at: https://doi.org/10.1109/12.88483.

BibTeX

@article{guan1991time,
  title = {{Time-space optimal parallel merging and sorting}},
  author = {Guan, Xiaojun and Langston, Michael A.},
  journal = {IEEE Transactions on Computers},
  volume = {40},
  number = {5},
  pages = {596--602},
  year = {1991},
  doi = {10.1109/12.88483}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.