Efficient radix sorting system employing a dynamic branch table

• US 5,396,622 A
• Filed: 12/23/1991
• Issued: 03/07/1995
• Est. Priority Date: 12/23/1991
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Lee, Paul K., Yehudai, Zvi Y.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Lintz, Paul R.
• Application Number:
  US07/813,246
• Time in Patent Office: 1,170 Days
• Field of Search: 395/600, 395/800, 395/700, 395/400, 395/650
• US Class Current: 1/1
• CPC Class Codes: G06F 7/24 Sorting, i.e. extracting data from one or more carriers, rearranging the data in numerical or other ordered sequence, and rerecording the sorted data on the original carrier or on a different carrier or set of carriers sorting methods in generalG06F7/36 takes precedence
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

In a recursive distributive sort of records according to their key fields, a method for distributing keys to form one or more subgroups and collecting them to preserve or maintain an order among the subgroups. The distribution is accomplished by comparing each key field against an extrinsic attribute and then assigning the key to a subgroup or bucket. The collection sequence preserves the overall key field order. A Dynamic Branching Table (DBT) for governing the ordering of buckets during the collection phase is initially populated with NO-OP instructions. During the distribution phase, a CALL instruction replaces the NO-OP in the sorted order DBT position upon the first occurrence of a distinguishable character in the key character sequence being scanned. An address pointer, pointing to the corresponding bucket, is then inserted in a Bucket Pointer Table (BPT) indexed to the DBT. During the collection phase, the DBT is executed and the empty buckets are skipped by NO-OP execution, while the populated buckets are processed by subroutine CALL execution.

Claims

1. In a computer-implemented method for distributively sorting a plurality of records by their key fields, said method including steps of recursively distributing and collecting said key fields, each recursion including the steps of (a) comparing each key field against an extrinsic attribute and assigning the key to a same-attribute subgroup, and (b) collecting the subgroups to create an interim or final key order, said recursions being repeated for all subgroups having more than one key field element, the location of all of said subgroups being maintained in a bucket address table of link-listed keys or pointers, wherein the improvement comprises the steps of:

creating a dynamic branching table (DBT) indexed by said bucket address table and initialized by NO-0P (no-operation) instructions;

during each said distribution step, populating said DBT with a CALL instruction linked to said bucket address table for each said subgroup having at least one said key field elements; and

during each said collecting step, executing said DBT such that said NO-OP instructions cause the skipping of each said subgroup having no said key field element and said CALL instructions cause the ordering of each said subgroup having at least one key field element.

2. A computer-implemented method for sorting records, said records having a least one key field controlling the sort ordering, said key field having one or more bytes of unique rank, each said byte having a value and all said bytes having the same radix, said method comprising the unordered steps of:

(a) creating a Dynamic Branching Table (DBT) indexed according to said key field byte value and rank, said DBT initially containing a NO-OP instruction in all locations;

(b) creating a Bucket Pointer Table (BPT) indexed according to said key field byte value and rank, said BPT initially containing a null datum in all locations;

(c) creating an input bucket containing all said key fields for said records to be sorted;

(d) distributing the contents of said input bucket to a plurality of output buckets according to the value of said key field byte of a present rank, said distributing step including the steps of;

(1) if said input bucket contains only a single key field, writing said single key field as the most recent entry to a collection bucket;

(2) if said input bucket contains at least two key fields, performing for each said key field in said input bucket, the unordered steps of

(i) ascertaining the value of said present rank key field byte for said each key field,

(ii) replacing said NO-OP instruction with a CALL instruction in said DBT location corresponding to said value and rank of said present rank key field byte, where said CALL instruction causes said distributing step (d) to be recursively repeated for at least one subsequent key field byte rank and a subsequent input bucket corresponding to an output bucket of said present rank,

(iii) writing said each key field to the one of said output buckets corresponding to said present rank key field byte value for said each key field, and

(iv) replacing said null datum with the address of said output bucket in the BPT location corresponding to the value and rank of said present rank key field byte; and

(3) executing each said DBT instruction having said present rank,

whereby said key fields are written in sorted order to said collection bucket.

3. The method of claim 2 wherein the third said creating step (c) further comprises the step of:

creating said input bucket to contain a plurality of Record Representations (RRs), said plurality including the key field for each of said records to be sorted.

4. The method of claim 2 wherein said executing step (d) (3) further comprises the step of:

replacing said CALL instruction in said DBT with a NO-OP instruction subsequent to execution of said CALL instruction.

5. In a bucket sorting method for computing equipment wherein keys, each formed by a plurality of characters, are ordered by successive iterations of processing into any of a number R of buckets, the steps comprising:

writing a CALL instruction into every location within a Dynamic Branch Table associated with any of the different characters of a subgroup of keys encountered during a current iteration through such subgroup, said Dynamic Branch Table being an executable code sequence, and said CALL instruction being a means for recursively sorting said keys in a subsequent said iteration; and

executing all said Dynamic Branch Table instructions in sequence after completion of said current iteration.

6. The method of claim 5 wherein:

each said Dynamic Branch Table location is initially filled with a NO-OP instruction, said NO-0P instruction being a means for advancing to a subsequent instruction within said Dynamic Branch Table.