Browse Prior Art Database

Sorting by the Logical Connection of Sequences

IP.com Disclosure Number: IPCOM000074664D
Original Publication Date: 1971-May-01
Included in the Prior Art Database: 2005-Feb-23
Document File: 3 page(s) / 20K

Publishing Venue

IBM

Related People

Bouroudjian, NA: AUTHOR

Abstract

This is a sort technique to eliminate unnecessary merging and improve performance when a forward or backward ordering is present in the file to be sorted.

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

Page 1 of 3

Sorting by the Logical Connection of Sequences

This is a sort technique to eliminate unnecessary merging and improve performance when a forward or backward ordering is present in the file to be sorted.

Sort programs usually have three phases; phase 1 uses some internal sorting technique to generate sequences; phase 2 merges these sequences as many times as may be necessary to reduce the number of sequences to a value known as "merge order"; phase 3 performs a final merge and writes the sorted file onto the output file. Some of the sequences produced by phase 1 may be treated as logical extensions of one another. Therefore, one may logically connect (concatenate) such sequences and consequently have fewer sequences to merge in phase 2. For example, the sort program may have generated sequences among which may be: physical sequence 1 = (17, 19, 20, 25, 32, 35), physical sequence 5 = (2, 3, 5, 9, 10, 12, 14, 15), and physical sequence 12 = (40, 41, 47, 48, 51, 53, 59).

Instead of treating the above sequences as three distinct sequences (which current sort programs do) one should, at the end of phase 1 of the sort, logically connect these sequences and treat them as one sequence since sequence 1 falls completely after sequence 5, and sequence 12 falls completely after sequence 1.

For a more precise description of the proposed technique, let n = the number of physical sequences generated by phase 1 of the sort program, and S(p) = (ps(1), ps(2), ps(3), ..., ps(i), ..., ps(n)), where ps(i) represents the ith physical sequence out of phase 1. Furthermore, let

ps(i) = (F(i), L(i)), where F(i) and L(i) represent the First and Last elements (records) of ps(i), respectively. Now, let ls be defined as the jth logical sequence such that

(Image Omitted)

As a result of logically connecting the physical sequence we get a new set of sequences.

S(1...