Browse Prior Art Database

Sorting Method

IP.com Disclosure Number: IPCOM000080643D
Original Publication Date: 1974-Jan-01
Included in the Prior Art Database: 2005-Feb-27
Document File: 8 page(s) / 136K

Publishing Venue

IBM

Related People

Parkinson, JC: AUTHOR

Abstract

Described is a method for sorting and combining records by programming a digital computer.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 22% of the total text.

Page 1 of 8

Sorting Method

Described is a method for sorting and combining records by programming a digital computer.

Figs. 1A and 1B are a flowchart of an internal sort phase that per permits a computer to sort individual records into sequences.

Fig. 2 is a flowchart for a merge phase that permits the computer to merge the sequences obtained from an internal sort phase. The following is a legend of the acronyms used herein:

WR Working record register, contains a record in the format used on the work device, and is made up of;

LR Logic record register, contains one of the records to be handled, which in turn contains its own key.

NK Next key register, contains the key of another record. CA Chaining address register, contains the address of a record on a work device.

SC Sequence control register, there are g such registers. Each of these registers includes the following parts:

SK Sequence key register, intended for the key of the latest record of a sequence.

SA Sequence address register, intended for the address of the latest record on the work device.

LC Length count register, intended for a count of the number of records in a sequence.

DE Directory entry register, there are d such registers. Each of these registers includes the following parts:

FK First key register, intended for the first record key in a sequence.

FA First address register, intended for the first record address.

RC Record count register, intended for a count of the number of records in a sequence.

NOA Next output address, contains the address of a record on a work device.

DSA Directory saved address, contains the address of a record on a work device.

LRA Last record address, in auxiliary register.

SCC Sequence control counter register, contains a count of sequence control registers with valid information.

SPC, SQC Sequence count registers, contains counts of sequences produced in the internal sort.

The functions found in the sorting phases are illustrated in Figs. 1A and 1B for the internal sort phase and to Fig. 2. for the merge phase.

In Fig. 1A and B, g sequences are generated during the internal sort phase. One control register SC is available for each sequence. Within each SC register, subregister SK includes the key for the last record, which was supplied to the sequence in the SC register. As soon as a new record has been read, it is

1

Page 2 of 8

assigned to the sequence where it fits best. A SC register is selected according to the key in its subregister SK.

In the following it is assumed that an ascending key sequence is obtained. The keys in the SC registers can then be regarded as dividing sequences of possible key values in g+1 sub-sequences, and a sub-sequence is selected within which each new key value fits. Each sub-sequence, except for the highest, is defined by the key at its upper end separating it from the next sub- sequence. When a suitable SC register is found, the new record is added to the included sequence and the key in subregister SK is modified t...