Browse Prior Art Database

Sorting Method

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

Publishing Venue

IBM

Related People

Lum, VY: AUTHOR [+3]

Abstract

This is a sorting method for sorting records using key distribution.

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

Page 1 of 2

Sorting Method

This is a sorting method for sorting records using key distribution.

In step 1, the bucket size is determined by dividing the core size by the record size.

In step 2, the total number of buckets is determined by dividing the total number of records in the file to be sorted by the bucket size from step 1.

In step 3, a table of key ranges for the buckets is created. This may be done, for example, by reading all of the keys from the file. (As only keys are needed, all other information is stripped from the records.) These are sorted by, for example, a tag sorting procedure. Once the keys have been sorted into numerical sequence, the bucket size or number of buckets is applied to that sequence to identify the key range for each bucket.

In step 4, the records in the file are read in and distributed according to their key values to the buckets. In an environment where the buckets are located on disks, as a sequential read or write is a great deal faster than a random read or write, the head movement will be minimized by blocking the writes in distributing records to buckets. Thus, for a given core size, it may not be possible to handle all the buckets in one pass, and the input file may have to be read more than one time. In each pass, then, only those records having keys in the ranges of those buckets being examined are used, and the others are ignored. The number of such read-in passes is preferably determined so that read-in time and bucket distributi...