Browse Prior Art Database

Bit Block Mapping For Sorting Records In A File

IP.com Disclosure Number: IPCOM000048714D
Original Publication Date: 1982-Mar-01
Included in the Prior Art Database: 2005-Feb-09
Document File: 1 page(s) / 12K

Publishing Venue

IBM

Related People

Chang, PY: AUTHOR [+3]

Abstract

There is a problem of efficiently sorting a file where there is such limited work space that only a sub set of the file fits into memory at a time and it is not possible to write back into the file. A bit block algorithm has been developed to handle this problem.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 67% of the total text.

Page 1 of 1

Bit Block Mapping For Sorting Records In A File

There is a problem of efficiently sorting a file where there is such limited work space that only a sub set of the file fits into memory at a time and it is not possible to write back into the file. A bit block algorithm has been developed to handle this problem.

On the first execution of the sort routine, the bit mapping is established where one bit represents one or more records in the file.

This is done as follows: The total number of records in the file is divided by the total number of bits available for mapping. This results in an integer plus remainder. If the remainder (R) is zero, then each bit represents a uniform number of records. If the remainder exists, then the bits 1 through R represent the integer + 1 amount of records. The remaining bits represent the integer number of records. Each bit in this case is as nearly uniform in number of records as possible.

A bit is set on (all bits are originally 0) as the records are searched sequentially, and any record represented by the bit is determined to qualify. At the same time, qualifying records are sorted into a limited work space called a bucket. If the bucket fills before all records are examined, then records are swapped in and out of the bucket until only the top records remain and all records have been examined. Sorted records from the bucket are passed to the output routine, and the last (worst-case printed) is kept in the bucket after sorting.

On su...