Importance

Loading Importance Indicators...

Abstract

A method is disclosed of sorting data in an electronic data processing system utilizing a digital computer and at least one random access device such as, for example, a magnetic disc or drum unit. A first simulation is performed to optimize the utilization of the resources of the data processing system. This simulation is based on information relating to characteristics of the data processing system available to the sorting function as well as known or predicted information concerning the data to be sorted. The input data is ordered into a plurality of strings of data which are generated by a selection technique known as quadratic selection replacement. The number of strings generated is minimized by determining if data bias exists, and if unfavorable or negative bias is discovered, the order of string generation is reversed. The ordered strings of data are written into random access storage in sets of ordered data blocks with each block having at least one link each to the data blocks logically positioned in front and in back thereof so that the logical position of each block in the string is well defined. After the initial string generation phase has been completed, the sequence in which the now existing strings will be selected for merging into fewer strings is computed so that the data in the strings will be manipulated a minimum number of times. The data blocks of the merged strings are then read into the working storage area of the digital computer where the data blocks are merged into still fewer strings. The working storage area is divided into a record hold area and generally, at least three buffers, an input buffer, an output buffer, and an active buffer from which the data is transferred into and from the record hold area. The order in which the data blocks already in the working storage area will become exhausted is maintained and hence the order in which new data blocks will be required is anticipated before they are needed. Thus, the read-write heads (hereinafter referred to as readheads) in the random access storage devices can be positioned at the proper track location for reading a required block before the block is needed. This is one result of the synchronization of read and write operations which thereby reduces the input/output time. This merge process is repeated until the number of strings has been reduced to a number equal to the order of the final merge. That number of strings is then read from the random access storage area into the working storage area of the computer and again merged until only one string or set of strings remains which string or set of strings contains the input data ordered in the desired sequence.

Loading the Abstract Image...

First Claim