Sort and merge system using tags associated with the current records being sorted to lookahead and determine the next record to be sorted

• US 5,349,684 A
• Filed: 07/22/1992
• Issued: 09/20/1994
• Est. Priority Date: 06/30/1989
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Digital Equipment Corporation (HP Inc.), National Semiconductor Corporation (Texas Instruments, Inc.)
• Inventors: Johnston, John T., Helliwell, Richard P., Edem, Brian C., Lary, Richard F.
• Primary Examiner(s): Lee, Thomas C.
• Assistant Examiner(s): ELLCESSOR, LARR
• Application Number:
  US07/918,871
• Time in Patent Office: 790 Days
• Field of Search: 364/DIG. 1, 364/DIG. 2, 395/600, 395/800, 340/146.2
• US Class Current: 1/1
• CPC Class Codes: G06F 7/36 Combined merging and sorting
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

A speed and memory control system and method for use with a sort accelerator having a rebound sorter. The speed and memory control system includes a variable length shift register which utilizes circulating RAM indexing, tag extraction lookahead features to speed up access of records, and merge lookahead and memory management features to provide quick and effective storage of records.

Claims

1. A sorting system for serially processing records comprising:

input means for serially supplying groups of unordered record;

sorting means for serially receiving said groups of unordered records from said input means and serially outputting strings of said records in sorted order;

output means for serially receiving said strings of sorted records from said sorting means and for serially storing said strings of sorted records;

sort control means having an initial mode and a merge mode of operation and being connected to said input means, said sorting means and said output means;

said sort control means operating in said initial mode to effect serial inputting of said unordered records from each of said groups from said input means to said sorting means and to effect storage of said strings of sorted records in said output means;

said sort control means thereafter operating in said merge mode to effect serial inputting of said sorted records from said strings of sorted records stored in said output means to said input means and from said input means to said sorting means for sorting of said sorted records from said strings into another string comprising all of said records of said strings in sorted order and to effect storage of said another string in said output means;

said sort control means having a sort sequencer means for operating in said merge mode to initially supply the smallest record of each of said strings of sorted records to said input means;

said input means having tagging means for adding to each of said sorted records a tag identifying the string into which each of said sorted records was sorted and serially supplying said sorted records with tags to said sorting means;

said sorting means serially receiving said sorted records with tags from said input means and having means for selecting one of said records to be outputted and for generating a signal indicating that one of said record has been selected and means, responsive to said indicating signal for examining the tag of said one of aid records in said sorting means that is about to be outputted before said one record is completely outputted from said sorting means and identifying the string into which said one record was sorted;

said sort sequencer means responsive to said identification of said string from said tag of said one record to be outputted to select the smallest of any remaining records in said identified string, which is the only record that could be smaller than any record in said sorting means, to be inputted to said sorting means;

said sort sequencer means responsive to said identification of said string from said tag of said one record to be outputted to determine when said identified string is empty and then to select the smallest record in any non-empty one of said strings to be inputted to said sorting means;

said sorting means sorting said records from said strings into said another string comprising all of said records of said strings in sorted order and serially outputting said another string of said records in sorted order;

said output means serially receiving said another string of sorted records from said sorting means and serially storing said another string of sorted records.

2. A method of serially sorting groups of unordered records into a composite string of records in sorted order using a sorter comprising the steps of:

a) serially receiving said groups of unordered records;

b) serially inputting the records of each group of unordered records into the sorter;

c) sorting the records of each group into strings of ordered records;

d) serially storing said strings of ordered records;

e) serially inputting to the sorter a new group of records comprising the smallest record from each of said strings of ordered records and adding to each of said smallest records a tag identifying the string into which each of said smallest records was sorted;

f) determining the smallest one of the records currently in the sorter;

g) selecting said smallest one of the records currently in the sorter to be outputted;

h) generating a signal within the sorter indicating that said smallest one of the records currently in the sorter has been selected;

i) examining, in response to said indicating signal, the tag of said smallest record currently in the sorter before said currently smallest record is completely outputted from the sorter and identifying said string into which said currently smallest record was sorted;

j) selecting the next record to be inputted to the sorter from said string identified by said tag of said currently smallest record unless said identified string is empty and then selecting as the next record to be inputted to the sorter the smallest record from any non-empty string of said strings of ordered records;

k) outputting said currently smallest record in the sorter;

l) inputting to the sorter said next record and adding to said next record a tag identifying said string into which said next record was sorted;

m) repeating steps f) through l) to form said composite string of ordered records comprising all of the records from said strings of ordered records.

3. A method of serially sorting groups of unordered records into a composite string of records in sorted order using a sorter comprising the steps of:

a) serially receiving said groups of unordered records;

b) serially inputting the records of each group of unordered records into the sorter;

c) sorting the records of each group into the string of ordered records;

d) serially storing said strings of ordered records;

e) serially inputting to the sorter a new group of records comprising the smallest record from each of said strings of ordered records and adding to each of said smallest records a tag identifying a string into which each of said smallest records was sorted;

f) determining the smallest one of the records currently in the sorter;

g) selecting said smallest one of the records currently in the sorter to be outputted;

h) generating a signal within the sorter indicating that said smallest one of the records currently in the sorter has been selected;

i) examining, in response to said indicating signal, the tag of said smallest record currently in the sorter before said currently smallest record is completely outputted from the sorter and identifying said string into which said currently smallest record was sorted;

j) selecting the next record to be inputted to the sorter from said string identified by said tag of said currently smallest record;

k) outputting said currently smallest record in the sorter;

l) determining if said identified string has another record or is empty;

m) serially inputting to the sorter the next record selected from said identified string if said identified string has another record and adding to said next record a tag identifying said string into which said next record was sorted;

n) selecting an artificial record larger than any record in said strings and inputting said artificial record into the sorter if said identified string is empty;

m) repeating steps f) through n) until said artificial record is outputted from said sorter to form said composite string of ordered records comprising all of the records from said strings of ordered records.