US 5,396,622 A · Efficient radix sorting system employing a dynamic branch table

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.

Claims6

Dependent claims

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.

1 more element

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.

10 more elements

Dependencies are inferred from the claim text.

Efficient radix sorting system employing a dynamic branch table

Life of this patent

Efficient radix sorting system employing a dynamic branch table

Life of this patent

Abstract

Claims6