Browse Prior Art Database

Sort Process

IP.com Disclosure Number: IPCOM000077614D
Original Publication Date: 1972-Aug-01
Included in the Prior Art Database: 2005-Feb-25
Document File: 3 page(s) / 42K

Publishing Venue

IBM

Related People

McKeller, AC: AUTHOR

Abstract

This distribution sort process is designed for sorting the records of a file in which each of the records has a key associated and the key value distribution is nonuniform.

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 53% of the total text.

Page 1 of 3

Sort Process

This distribution sort process is designed for sorting the records of a file in which each of the records has a key associated and the key value distribution is nonuniform.

The process effects the sorting of a file consisting of n records stored on a secondary storage such as magnetic tape, disk or drum, by which a copy of the sorted file is produced on a similar secondary storage.

Block 10 sets forth the purpose of the program, i.e. to sort a file consisting of n records X(1) - X(n). The first phase is constituted by from the file and in step 14, the sample is sorted to obtain the sequence Y(1) to Y(sl+s-1), l+1 being the quantity of subsets desired in a distribution pass and s a selectable parameter.

The second phase is set forth in step 16, which is the partitioning of the file into l+1 subsets, So to Sl, where Si is that subset of the original file which consists of all the records X(j), the keys of which are greater than or equal to the Y(is)th key from the sorted sample and less than the Y{(i+1)s}th key from the sorted sample. In step 18, i is set to zero, i representing the current subset being considered, i.e. So.

In step 20, the test is made as to whether G, which is the quantity of records which can be accommodated in the main store available for the sort, is greater than or equal to the size of Si, i.e. So. to this purpose step 16 also includes the keeping track of the quantity of records which constitute each subset. If step 20 results in a yes, the program moves to step 24 in which the records in subset So will be sorted. If step 20 results in a no, the program moves to step 22 where a random sample will be selected from the subset Si as set forth in step 12. Such sample will be sorted as set forth in step 14 and the subset will be partitioned according to step 16, producing sub-subsets which will be sorted by steps 18-30.

Considering the situation where the program moved from step 20 to 24, with the completion of step 24, the program moves to step 26 where the sorted subset Si, in this case So, is concatenated with other subsets. Since this is the first subse...