Sorting in linear time?

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Sorting in linear time?

Full text

Pdf (1.25 MB)

Source

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

Las Vegas, Nevada, United States

Pages: 427 - 436

Year of Publication: 1995

ISBN:0-89791-718-9

Authors

Arne Andersson	Department of Computer Science, Lund University, Box 118, S-22100 Lund, Sweden
Torben Hagerup	Max-Planck-Institut für Infomatik, D-66123 Saarbrücken, Germany
Stefan Nilsson	Department of Computer Science, Lund University, Box 118, S-22100 Lund, Sweden
Rajeev Raman	Department of Computer Science, King's college London, Strand, London WC2R 2LS, U.K.

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 10, Downloads (12 Months): 81, Citation Count: 20

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/225058.225173 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	M. Ajtai , J. Komlós , E. Szemerédi, An 0(n log n) sorting network, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.1-9, December 1983 [doi>10.1145/800061.808726]
	2	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
	3	A. Andersson and S. Nilsson. A new efficient radix sort. In Proc. 35th Annual IEEE Symp. on Foundations of Computer Science, pp. 714-721, 1994.
	4	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]
	5	A. M. Ben-Amram and Z. Galil. When can we sort in o(n log n) time? In Proc. 34th Annual IEEE Symp. on Foundations of Computer Science, pp. 538-546, 1993.
	6	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]
	7	Richard Cole , Uzi Vishkin, Approximate parallel scheduling. Part I: the basic technique with applications to optimal parallel list ranking in logarithmic time, SIAM Journal on Computing, v.17 n.1, p.128-142, Feb. 1988 [doi>10.1137/0217009]
	8	M. Dietzfelbinger, T. Hagerup, J. Katajainen, and M. Penttonen. A reliable randomized algorithm for the closest-pair problem. Tech. Rep. no. 513, Fachbereich Informatik, Universitat Dortmund, 1993.
	9	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]
	10	Harold N. Gabow , Jon Louis Bentley , Robert E. Tarjan, Scaling and related techniques for geometry problems, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.135-143, December 1984 [doi>10.1145/800057.808675]
	11	Torben Hagerup, Optimal parallel string algorithms: sorting, merging and computing the minimum, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.382-391, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195202]
	12	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]
	13	David A. Patterson , John L. Hennessy, Computer organization & design: the hardware/software interface, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
	14	D. Kirkpatrick and S. Reisch. Upper bounds for sort-ing integers on random access machines. Theoret. Com-puter Science, 28, pp. 263-276, 1984.
	15	Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
	16	C. P. Kruskal. Searching, merging, and sorting in par-allel computation. IEEE Trans. Comput., 32, pp. 942- 946, 1983.
	17	F. Thomson Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
	18	W. J. Paul and J. Simon. Decision trees and random ac-cess machines. In Proc. International Symp. on Logic and Algorithmic, Zurich, pp. 33 1-340, 1980.
	19	R. E. Tarjan and U. Vkhkin. An efficient parallel bicon-nectivity algorithm. SIAMJ. Comput., 14, pp. 862-874, 1985.

CITED BY 22

	Yijie Han , Xiaojun Shen, Parallel integer sorting is more efficient than parallel comparison sorting on exclusive write PRAMs, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.419-428, January 17-19, 1999, Baltimore, Maryland, United States
	Gudmund Skovbjerg Frandsen , Johan P. Hansen , Peter Bro Miltersen, Lower bounds for dynamic algebraic problems, Information and Computation, v.171 n.2, p.333-349, December 15, 2001
	Mikkel Thorup, On RAM priority queues, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.59-67, January 28-30, 1996, Atlanta, Georgia, United States
	Mikkel Thorup, Faster deterministic sorting and priority queues in linear space, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.550-555, January 25-27, 1998, San Francisco, California, United States
	Noga Alon , Martin Dietzfelbinger , Peter Bro Miltersen , Erez Petrank , Gábor Tardos, Linear hash functions, Journal of the ACM (JACM), v.46 n.5, p.667-683, Sept. 1999
	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
	Lars Arge , Paolo Ferragina , Roberto Grossi , Jeffrey Scott Vitter, On sorting strings in external memory (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.540-548, May 04-06, 1997, El Paso, Texas, United States
	Noga Alon , Martin Dietzfelbinger , Peter Bro Miltersen , Erez Petrank , Gábor Tardos, Is linear hashing good?, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.465-474, May 04-06, 1997, El Paso, Texas, United States
	Yijie Han, Deterministic sorting in O(nlog logn) time and linear space, Journal of Algorithms, v.50 n.1, p.96-105, January 2004
	Thore Husfeldt , Theis Rauhe , Søren Skyum, Lower bounds for dynamic transitive closure, planar point location, and parantheses matching, Nordic Journal of Computing, v.3 n.4, p.323-336, Winter 1996
	Mikkel Thorup, Randomized sorting in O(n log log n) time and linear space using addition, shift, and bit-wise boolean operations, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.352-359, January 05-07, 1997, New Orleans, Louisiana, United States
	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
	Yijie Han, Improved fast interger sorting in linear space, Information and Computation, v.170 n.1, p.81-94, October 10, 2001
	Mikkel Thorup, Undirected single-source shortest paths with positive integer weights in linear time, Journal of the ACM (JACM), v.46 n.3, p.362-394, May 1999
	Rina Panigrahy , Samar Sharma, Sorting and Searching using Ternary CAMs, IEEE Micro, v.23 n.1, p.44-53, January 2003
	Christophe Cérin , Michel Koskas , Hazem Fkaier , Mohamed Jemni, Sequential in-core sorting performance for a SQL data service and for parallel sorting on heterogeneous clusters, Future Generation Computer Systems, v.22 n.7, p.776-783, August 2006
	Yijie Han, Deterministic sorting in O(nlog log n) time and linear space, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Alejandro López-Ortiz , Mehdi Mirzazadeh , Mohammad Ali Safari , Hossein Sheikhattar, Fast string sorting using order-preserving compression, Journal of Experimental Algorithmics (JEA), 10, 2005
	P. Berman , M. Karpinski , Y. Nekrich, Approximating Huffman codes in parallel, Journal of Discrete Algorithms, v.5 n.3, p.479-490, September, 2007
	Kunihiko Sadakane, Succinct data structures for flexible text retrieval systems, Journal of Discrete Algorithms, v.5 n.1, p.12-22, March, 2007
	Milan Ružić, Making deterministic signatures quickly, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.900-909, January 07-09, 2007, New Orleans, Louisiana
	Kimmo Fredriksson , Veli Mäkinen , Gonzalo Navarro, Rotation and lighting invariant template matching, Information and Computation, v.205 n.7, p.1096-1113, July, 2007