The Ford-Johnson Sorting Algorithm Is Not Optimal

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback
Take a look at the new version of this page: [ beta version ]. Tell us what you think.

The Ford-Johnson Sorting Algorithm Is Not Optimal

Full text

Pdf (887 KB)

Source

Journal of the ACM (JACM) archive
Volume 26 , Issue 3 (July 1979) table of contents

Pages: 441 - 456

Year of Publication: 1979

ISSN:0004-5411

Author

Glenn K. Manacher

Department of Information Engineering, University of Illinois at Chicago Circle, Computer Center, Box 4348, Chicago, IL

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 34, Citation Count: 4

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/322139.322145 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	FORD, L R JR, AND JOHNSON, S B A tournament problem AMM 66, 5 (1959), 387-389
	2	GRAHAM, R L, On sorting by comparisons Proc Second Atlas Conf, 1971, pp 263-269
	3	HADIAN, A Thesis, U of Minnesota, Minneapolis, Mmn, 1969
	4	HWANG, F K, AND LIN, S An analysis of Ford and Johnson's sorting algorithm Proc Third Annual Princeton Conf on Inform Scl and Syst, 1969, pp 292-296
	5	HWANG, F K, AND LIN, S Optimal merging of two elements with n elements Acta lnforrnatlca 1 (1971), 145-158
	6	HWANG, F K, AND LIN, S A simple algorithm for merging two disjoint hnearly-ordered sets SIAM J Comptng 1, 1 (1972), 31-39
	7	HWANG, F K, AND LIN, S Some opumahty results in merging two disjoint linearly-ordered sets Memo, Bell Laboratories, Murray Hill, N.J, 1972
	8	HWANG, F K, AND LIN, S Unpublished note Described in Knuth {9}, problem 5 3 2-14
	9	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
	9a	KNUTH, D E., AND KAEHLER, E B An experiment in optimal sorting IPL 1 (1972), pp 173-176
	10	Glenn K. Manacher, Significant Improvements to the Hwang-Lin Merging Algorithm, Journal of the ACM (JACM), v.26 n.3, p.434-440, july 1979 [doi>10.1145/322139.322144]
	11	WELLS, M Applications of a language for computing In combmatoncs Information Processing 65 (Proc 1965 IFIP Cong ), North-Holland, Amsterdam, 1966, pp 497--498

CITED BY 4

	Glenn K. Manacher, Significant Improvements to the Hwang-Lin Merging Algorithm, Journal of the ACM (JACM), v.26 n.3, p.434-440, july 1979
	G. K. Manacher , T. D. Bui , T. Mai, Optimum combinations of sorting and merging, Journal of the ACM (JACM), v.36 n.2, p.290-334, April 1989
	Marcin Peczarski, The Ford--Johnson algorithm still unbeaten for less than 47 elements, Information Processing Letters, v.101 n.3, p.126-128, February, 2007
	Mauricio Ayala-Rincón , Bruno T. de Abreu , José de Siqueira, A variant of the Ford--Johnson algorithm that is more space efficient, Information Processing Letters, v.102 n.5, p.201-207, May, 2007