Research and Advances

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.

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 does not lend itself to sophisticated techniques.

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 from input formats, (2) their reconversion to output formats, and (3) comparison techniques between internal formats.