Parallel integer sorting is more efficient than parallel comparison sorting on exclusive write PRAMs

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Parallel integer sorting is more efficient than parallel comparison sorting on exclusive write PRAMs

Full text

Pdf (1.28 MB)

Source

Symposium on Discrete Algorithms archive
Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms table of contents

Baltimore, Maryland, United States

Pages: 419 - 428

Year of Publication: 1999

ISBN:0-89871-434-6

Authors

Yijie Han	Electronic Data Systems, Inc., 750 Tower Drive, CPS, Mail Stop 7121, Troy, MI
Xiaojun Shen	Computer Science Telecommunications Program, University of Missouri, Kansas City, 5100 Rockhill Road Kansas City, MO

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIAM : Society for Industrial and Applied Mathematics

Publisher

Society for Industrial and Applied Mathematics Philadelphia, PA, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 22, Citation Count: 3

Additional Information:

references cited by index terms collaborative colleagues

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

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	M. Ajtai , J. Komlós , E. Szemerédi, Sorting in c log n parallel steps, Combinatorica, v.3 n.1, p.1-19, Jan. 1983 [doi>10.1007/BF02579338]
	2	Susanne Albers , Torben Hagerup, Improved parallel integer sorting without concurrent writing, Information and Computation, v.136 n.1, p.25-51, July 10, 1997 [doi>10.1006/inco.1997.2632]
	3	A. Andersson, Faster deterministic sorting and searching in linear space, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.135, October 14-16, 1996
	4	Arne Andersson , Torben Hagerup , Stefan Nilsson , Rajeev Raman, Sorting in linear time?, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.427-436, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225173]
	5	R. Anderson and G. Miller, Deterministic parallel list ranking, .Mgorithmica, 6, 859-868(1991).
	6	P. Beame , J. Hastad, Optimal bounds for decision problems on the CRCW PRAM, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.83-93, January 1987, New York, New York, United States [doi>10.1145/28395.28405]
	7	V. E. Benes, Mathematical Theory of Connecting Networks and Telephone Tra#c, New York: Academic, 1965.
	8	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]
	9	Richard Cole, Parallel merge sort, SIAM Journal on Computing, v.17 n.4, p.770-785, August 1988 [doi>10.1137/0217049]
	10	Stephen Cook , Cynthia Dwork , Ru&duml;ger Reischuk, Upper and lower time bounds for parallel random access machines without simultaneous writes, SIAM Journal on Computing, v.15 n.1, p.87-97, Feb. 1986 [doi>10.1137/0215006]
	11	Anders Dessmark , Andrzej Lingas, Improved bounds for integer sorting in the EREW PRAM model, Journal of Parallel and Distributed Computing, v.48 n.1, p.64-70, Jan. 1998 [doi>10.1006/jpdc.1997.1401]
	12	Michael L. Fredman , Dan E. Willard, Surpassing the information theoretic bound with fusion trees, Journal of Computer and System Sciences, v.47 n.3, p.424-436, Dec. 1993 [doi>10.1016/0022-0000(93)90040-4]
	13	Andrew V. Goldberg , Serge A. Plotkin , Gregory E. Shannon, Parallel symmetry-breaking in sparse graphs, SIAM Journal on Discrete Mathematics, v.1 n.4, p.434-446, Nov. 1988 [doi>10.1137/0401044]
	14	Torben Hagerup, Towards optimal parallel bucket sorting, Information and Computation, v.75 n.1, p.39-51, October 1, 1987 [doi>10.1016/0890-5401(87)90062-9]
	15	Torben Hagerup , H. Shen, Improved nonconservative sequential and parallel integer sorting, Information Processing Letters, v.36 n.2, p.57-63, Oct. 1990 [doi>10.1016/0020-0190(90)90097-H]
	16	Y. Han, Matching partition a linked list and its optimization, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.246-253, June 18-21, 1989, Santa Fe, New Mexico, United States [doi>10.1145/72935.72961]
	17	Y. Han, An optimal linked list prefix algorithms on a local memory computer, Proceedings of the 17th conference on ACM Annual Computer Science Conference, p.278-286, February 21-23, 1989, Louisville, Kentucky [doi>10.1145/75427.75462]
	18	Yijie Han , Xiaojun Shen, Conservative Algorithms for Parallel and Sequential Integer Sorting, Proceedings of the First Annual International Conference on Computing and Combinatorics, p.324-333, August 24-26, 1995
	19	Joseph JáJá, An introduction to parallel algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1992
	20	D. KLrkpatrick and S. Reisch, Upper bounds .for sorting integers on random access machines, Theoretical Computer Science 28, 263-276(1984).
	21	Clyde P. Kruskal , Larry Rudolph , Marc Snir, A complexity theory of efficient parallel algorithms, Theoretical Computer Science, v.71 n.1, p.95-132, 13 March 1990 [doi>10.1016/0304-3975(90)90192-K]
	22	Tom Leighton, Tight bounds on the complexity of parallel sorting, IEEE Transactions on Computers, v.34 n.4, p.344-354, April 1985 [doi>10.1109/TC.1985.5009385]
	23	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]
	24	Sanguthevar Rajasekaran , Sandeep Sen, On parallel integer sorting, Acta Informatica, v.29 n.1, p.1-15, Feb. 1992 [doi>10.1007/BF01178563]
	25	R. Vaidya-uathan, C. R. P. Haxtmann, P. K. Vaxshney, Towards optimal parallel radix sorting, Proc. 7th International Parallel Proc#g Symposium, 193- 197(1993).
	26	R.A. Wagner and Y. Has, Parallel algorithms for bucket sorting and the data dependent prefix problem, Proc. 1986 International Conf. on Parallel Processing, 924-930(1986).
	27	James C. Wyllie, The Complexity of Parallel Computations, Cornell University, Ithaca, NY, 1979

CITED BY 3

	Ka Wong Chong , Yijie Han , Yoshihide Igarashi , Tak Wah Lam, Improving the efficiency of parallel minimum spanning tree algorithms, Discrete Applied Mathematics, v.126 n.1, p.33-54, March 2003
	Yijie Han, Improved fast interger sorting in linear space, Information and Computation, v.170 n.1, p.81-94, October 10, 2001
	Yijie Han, Improved fast integer sorting in linear space, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.793-796, January 07-09, 2001, Washington, D.C., United States