Design and characteristics of a variable-length record sort using new fixed-length record sorting techniques

ABSTRACT

This paper describes the application of several new techniques for sorting fixed-length records to the problem of variable-length record sorting. The techniques have been implemented on a Sylvania 9400 computer system with 32,000 fixed-length words of memory. Specifically, the techniques sequence variable-length records of unrestricted size, produce long initial strings of data, merge strings of data at the power of T - 1, where T is the number of work tapes in a system, and do not restrict the volume of input data.

REFERENCES

• 1: Radio Corporation of America, Astro Electronics Division, and Applied Data Research, Inc. 1961. Design specifications for ACSI-MATIC sort and merge system. Report No. SR-61-3, prepared for Office, Assistant Chief of Staff for Intelligence, Department of the Army, Washington, D. C., June 1961.
• 2: MILLER, L.; MINKER, J.; REED, W. G.; SHINDLE, W. E. A multi-level file structure for information processing. Proc. Western Joint Comput. Conf., Apr., 1960.
• 3: COOKE, WILLIAM S. Optimum tape merging. Comm. ACM g (May 1963).
• 4: NOBEL, S. Oscillating sort-a new merge sorting technique. Comm. ACM 2 (1962), 30-32.
• 5: Martin A. Goetz, Internal and tape sorting using the replacement-selection technique, Communications of the ACM, v.6 n.5, p.201-206, May 1963 [doi>10.1145/366552.366556]