Internal and tape sorting using the replacement-selection technique

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Internal and tape sorting using the replacement-selection technique

Full text

Pdf (500 KB)

Source

Communications of the ACM archive
Volume 6 , Issue 5 (May 1963) table of contents

Pages: 201 - 206

Year of Publication: 1963

ISSN:0001-0782

Author

Martin A. Goetz

Applied Data Research, Inc., Princeton, NJ

Publisher

ACM New York, NY, USA

Bibliometrics

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

Additional Information:

abstract references cited by 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/366552.366556 What is a DOI?

ABSTRACT

A general technique for sequencing unsorted records is presented. The technique is shown to be applicable for the first stage of a generalized sort program (the formation of initial strings) as well as for sorting records within a memory storage (an internal sort). It is shown that given N records in memory storage, records are sequenced using 1+log2 N tests per record, that initial string lengths will average 2N for random input records, and that reading, writing and processing can be accomplished simultaneously if the computer permits such overlap.

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	GASSNER, BETTY JANE. Proof of a conjecture concerning sorting by replacement selection. Unpublished paper, 1958.
	2	Kenneth E. Iverson, A Programming Language., John Wiley & Sons, 1962
	3	R. C. Bose , R. J. Nelson, A Sorting Problem, Journal of the ACM (JACM), v.9 n.2, p.282-296, April 1962 [doi>10.1145/321119.321126]
	4	D. L. Shell, A high-speed sorting procedure, Communications of the ACM, v.2 n.7, p.30-32, July 1959 [doi>10.1145/368370.368387]

CITED BY 4

	W. A. Martin, Sorting, ACM Computing Surveys (CSUR), v.3 n.4, p.147-174, Dec. 1971
	Martin A. Goetz, Organization and structure of data on disk file memory systems for efficient sorting and other data processing programs, Communications of the ACM, v.6 n.5, p.245-248, May 1963
	Martin A. Goetz, Design and characteristics of a variable-length record sort using new fixed-length record sorting techniques, Communications of the ACM, v.6 n.5, p.264-267, May 1963
	Martin A. Goetz, Some improvements in the technology of string merging and internal sorting, Proceedings of the April 21-23, 1964, spring joint computer conference, April 21-23, 1964, Washington, D.C.

Collaborative Colleagues:

Martin A. Goetz: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player