IMPROVED METHOD OF PERFORMING A HIGH-PERFORMANCE SORT WHICH GAINS EFFICIENCY BY READING INPUT FILE BLOCKS SEQUENTIALLY

An improved method of performing a sort-merge operation on a digital computer is disclosed, which gains efficiency by reading input file blocks sequentially. The method takes into consideration the fact that records can be read in any order if they are subsequently to be sorted. Input from disk is processed by reading the working disk directory maintained by the operating system to determine all of the blocks associated with the input data to be sorted. The data block identities so determined are sorted in accordance with their physical location on the disk, thereby providing a sequential order for reading. The input data is read in this sequential order, and then, using largely conventional methods, sorted into one or more strings and merged as necessary to form the fully sorted output. Since the original record order in the file is known from the working directory that has been read, that order can be utilized if and as necessary, for example to preserve the original order of records with equal keys.