Constant-time parallel integer sorting

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Constant-time parallel integer sorting

Full text

Pdf (791 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-third annual ACM symposium on Theory of computing table of contents

New Orleans, Louisiana, United States

Pages: 299 - 306

Year of Publication: 1991

ISBN:0-89791-397-3

Author

Torben Hagerup

Max-Planck-Institut fu¨r Informatik, Saarbrucken, Germany

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 14, Citation Count: 5

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/103418.103452 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Paul Beame , Johan Hastad, Optimal bounds for decision problems on the CRCW PRAM, Journal of the ACM (JACM), v.36 n.3, p.643-670, July 1989 [doi>10.1145/65950.65958]
	2	P. C. P. Bhatt , K. Diks , T. Hagerup , V. C. Prasad , T. Radzik , S. Saxena, Improved deterministic parallel integer sorting, Information and Computation, v.94 n.1, p.29-47, Sept. 1991 [doi>10.1016/0890-5401(91)90031-V]
	3	Richard Cole , Uzi Vishkin, Faster optimal parallel prefix sums and list ranking, Information and Computation, v.81 n.3, p.334-352, June 1989 [doi>10.1016/0890-5401(89)90036-9]
	4	David Eppstein , Zvi Galil, Parallel algorithmic techniques for combinatorial computation, Annual review of computer science: vol. 3, 1988, Annual Reviews Inc., Palo Alto, CA, 1988
	5	Fănică Gavril, Merging with parallel processors, Communications of the ACM, v.18 n.10, p.588-591, Oct. 1975 [doi>10.1145/361020.361216]
	6	J. Gil , F. Meyer auf der Heide , A. Wigderson, Not all keys can be hashed in constant time, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.244-253, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100247]
	7	Torben Hagerup , T. Radzik, Every robust CRCW PRAM can efficiently simulate a PRIORITY PRAM, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.117-124, July 02-06, 1990, Island of Crete, Greece [doi>10.1145/97444.97677]
	8	Torben Hagerup , C. Rüb, A guided tour of Chernoff bounds, Information Processing Letters, v.33 n.6, p.305-308, February 1990 [doi>10.1016/0020-0190(90)90214-I]
	9	Torben Hagerup, Fast parallel generation of random permutations, Proceedings of the 18th international colloquium on Automata, languages and programming, p.405-416, June 1991, Madrid, Spain
	10	KARP, R.M. (1988), The Probabilistic Analysis of Combinatorial Algorithms, class notes, Univ. California, Berkeley.
	11	Yossi Matias , Uzi Vishkin, Converting high probability into nearly-constant time—with applications to parallel hashing, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.307-316, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103453]
	12	P. Ragde, The parallel simplicity of compaction and chaining, Proceedings of the seventeenth international colloquium on Automata, languages and programming, p.744-751, July 1990, Warwick University, England
	13	S. Rajasekaran , J. H. Reif, Optimal and sublogarithmic time randomized parallel sorting algorithms, SIAM Journal on Computing, v.18 n.3, p.594-607, June 1989 [doi>10.1137/0218041]
	14	RAMAN, R. (1991), The Power of Collision: Randomized Parallel Algorithms for Chaining and Integer Sorting, Tech. Rep. no. 336, Univ. of Rochester, March 1990 (revised January 1991).

CITED BY 5

	Susanne Albers , Torben Hagerup, Improved parallel integer sorting without concurrent writing, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.463-472, September 1992, Orlando, Florida, United States
	Michael T. Goodrich , Yossi Matias , Uzi Vishkin, Optimal parallel approximation for prefix sums and integer sorting, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.241-250, January 23-25, 1994, Arlington, Virginia, United States
	Torben Hagerup , Rajeev Raman, Fast deterministic approximate and exact parallel sorting, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.346-355, June 30-July 02, 1993, Velen, Germany
	Bogdan S. Chlebus , Dariusz R. Kowalski, Randomization helps to perform independent tasks reliably, Random Structures & Algorithms, v.24 n.1, p.11-41, January 2004
	Yossi Matias , Uzi Vishkin, Converting high probability into nearly-constant time—with applications to parallel hashing, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.307-316, May 05-08, 1991, New Orleans, Louisiana, United States