Sign In

Communications of the ACM

Table of Contents


Sorting on computers


Internal and tape sorting using the replacement-selection technique

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 …

An empirical study of minimal storage sorting


Multiphase sorting

With a limited number of tape drives available for sorting, the polyphase technique of merging provides faster sorting than the conventional balanced method of merging. This paper is an attempt to describe the polyphase method …

String distribution for the polyphase sort


Read-backward polyphase sorting

Read-backward Polyphase sorting provides more efficient use of the tapes available to a sort than most other sorting techniques. Backward Polyphase produces a continuous merging process from n - 1 tapes where n is the total number …

A comparison between the polyphase and oscillating sort techniques

Read-backward Polyphase sorting provides more efficient use of the tapes available to a sort than most other sorting techniques. Backward Polyphase produces a continuous merging process from n - 1 tapes where n is the total number …

Computer planned collates

Little effort has been directed toward the creation of efficient, easy-to-use file merging routines. This lack of effort undoubtedly stems from the feeling that a process as simple and straightforward as merging two or more files …

A tape file merge pattern generator

A routine is presented which specifies the sequence of merge cycles to effect the merging of sorted tape files. The routine is designed to minimize elapsed computer time by varying the power of the merge cycles, so as to use  …

Sorting nonredundant files—techniques used in the FACT compiler

Some typical file structures, including some called “non-redundant,” are examined, and the methods used in FACT to sort such files are discussed.

Sorting with large volume, random access, drum storage

An approach to sorting records is described using random access drum memory. The Sort program described is designed to be a generalized, self-generating sort, applicable to a variety of record statements. This description is  …

Organization and structure of data on disk file memory systems for efficient sorting and other data processing programs

An approach to the organization and structure of data on Bryant Disc File Memory Systems for sorting and performing other data processing functions is presented. The following areas are covered: characteristics of Bryant Disc …

Some characteristics of sorting computing systems using random access storage devices

The substantial differences in characteristics of random access storage and tape devices dictate that concepts and objectives of computer program design be considered from the viewpoint of the external file medium used. This  …

The COBOL sorting verb

The COBOL-61 specifications have recently been augmented with a number of extensions, one of which is a SORT verb. COBOL was designed initially for use in the processing of data-files stored on serially-accessed input-output  …

A method of comparing the time requirements of sorting methods

Formulas have been developed for estimating the sorting time required by most of the known internal sorting methods in terms of parameters describing the file to be sorted and the computer time required for basic sorting operations …

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

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 …

Conversion, reconversion and comparison techniques in variable-length sorting

The logic is described for converting highly variable input records into a format that can be easily and efficiently processed by a sorting program.1 The internal record formats are discussed in relation to (1) their conversion …

Use of tree structures for processing files

In data processing problems, files are frequently used which must both be searched and altered. Binary search techniques are efficient for searching large files, but the associated file organization is not readily adapted tos …