Sorting method

• US 4,611,280 A
• Filed: 03/12/1984
• Issued: 09/09/1986
• Est. Priority Date: 03/12/1984
• Status: Expired due to Term

• Current Assignee: NCR Corporation (NCR Voyix Corporation)
• Original Assignee: AT&T, Inc.
• Inventors: Linderman, John P.
• Primary Examiner(s): Eng, David Y.
• Application Number:
  US06/588,231
• Time in Patent Office: 911 Days
• Field of Search: 364/200, 364/900, 364/300
• US Class Current: 712/300
• CPC Class Codes: G06F 7/08 Sorting, i.e. grouping record carriers in numerical or other ordered sequence according to the classification of at least some of the information they carry by merging two or more sets of carriers in ordered sequence G06F7/16

Abstract

A sorting method for ordering information records according to the contents of one or more sort fields of the records. A sort key is the form of a character string is generated for each record according to a disclosed algorithm and the ordering of the records is performed according to a simple character-by-character sorting of the sort keys. Each of the sort fields may be of variable length and any sort field of any record may contain any number, including zero, of individual sort strings, referred to herein as sort objects.

Claims

1. A method of sorting information records in accordance with the contents of one or more specified sort fields for each record, in which any of the specified sort fields may contain any number of sort objects and in which sort objects may vary in length, the method comprising the steps of

A. assigning for each successive specified sort field a next one of a set of lexicographically ordered field keys,

B. generating a sort key for each record by

B1. initializing the sort key to a prescribed initial state,

B2. for a first sort field in the record containing at least one sort object, appending to the present sort key the assigned field key,

B3. appending to the present sort key a character string derived from a first sort object of the field, the resulting appendage from steps B2 and B3 having the characteristic that it is not a valid prefix of a character string derived from any other sort object in the corresponding sort field of another of the records,

B4. repeating steps B2 and B3 for each sort object of the first sort field, repeating steps B2, B3 and B4 for each successive specified sort field,

B5. appending to the present sort key a different terminating field key selected from the set of lexicographically ordered field keys, and

C. ordering the records according to a lexicographic comparison of their sort keys.

2. The invention of claim 1 wherein step (A) further comprises

assigning successive field keys monotonically decreasing in value to successive ones of the specified sort fields for which records are to be ordered in an ascending direction.

3. The invention of claim 1 wherein step (A) further comprises

assigning successive field keys monotonically increasing in value to successive ones of the specified sort fields for which records are to be ordered in a descending direction.

4. The invention of claim 1 wherein step (A) further comprises

assigning field keys monotonically descreasing in value to successive ones of the specified sort fields for which records are to be ordered in an ascending direction, and

assigning field keys monotonically increasing in value to successive ones of the remaining specified sort fields.

5. The invention of claim 4 wherein step B5 further comprises the step of

appending to the present sort key a terminating field key having a value between the values of the last assigned increasing and decreasing field keys.

6. The invention of claim 1 wherein for ASCII encoded records, step B3 further comprises the steps of

appending the contents of the sort object to the field key for ones of the sort fields for which sorting is to be in ascending lexicographic order, and

appending immediately after the contents of the sort object a delimiter having a value of zero.

7. The invention of claim 1 wherein for ASCII encoded records, step B3 further comprises the step of

appending the complement of the contents of the sort object to the field key for ones of the sort fields for which sorting is to be in descending lexicographic order, and

appending immediately after the contents of the sort object a delimiter having a value equal to the complement of the value zero.

8. The invention of claim 1 wherein the step B3 further comprises

determining if a sort object, if any, of the sort field is constrained to be of fixed length, and, if so, appending the contents of the present sort object.

9. The invention of claim 1 wherein step B3 further comprises determining if a sort object, if any, is of fixed length, and if not,

determining if the object is encoded in ASCII format, and, if not,

encoding the sort object according to a prescribed algorithm, in which the resulting encoding satisfies the characteristic that it is not a valid prefix of a character string derived from any other sort object in the corresponding sort fields of another of the records.

10. The invention of claim 9 wherein the step of encoding the sort object further comprises

partitioning the sort object into a plurality of substrings each having a prescribed length,

inserting a fill character containing all ones between consecutive substrings,

in the last substring, appending a sufficient number of padding characters each having a value of 0 to make the length of the last substring equal to the prescribed length, and

appending to the last substring a character specifying the number of nonpadding characters in the last substring.