US5615366A
Expired / Lapsed
US
⏱️ 0.0 years remaining
System and methods for improved sorting
Assignee: Borland Software Corp
•
Filing: 1996-06-11
•
Granted: 1997-03-25
•
Expires: 2016-06-11
Abstract
Abstract System and methods are described for sorting information records in a fast and efficient manner. The present invention is particularly useful in environments where resources, such as available memory storage, are limited. A preferred method of the present invention includes scanning the field of records to be sorted (e.g., from left to right), whereby the system recursively divides the records into smaller groups, as determined by the values at a current position (i.e., the location currently under examination). As the members of a group drop below a predetermined threshold value, traditional improved sorting techniques (e.g., quicksort or insertsort) may be applied to the group to complete the sort.
Inventors
- 👤 Kurt Hansen
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 14:08
CPC Classifications
G; G06; G06F; G06F7/00; G06F7/22; G06F7/24
Claims Analysis
Total Claims: 25
Claim 1
Independent Claim
251 words
In a computer system, an improved method for sorting a plurality of information records into a desired sequence, some of said information records storing at least two data members, some of the information records storing data members which are not identical from one data member of the record to another, the method comprising: (a) determining for each record a value for the first data member; (b) arranging the records into groups according to the value determined for the first data member of each record, wherein records having an identical value for the first data member are grouped together, and wherein at least some of said information records still remain to be sorted into said desired sequence; (c) further dividing each group into smaller groups by repeating steps (a)-(b) for each one of subsequent data members of each record of each group, so that within any given group all records of the group share a common part said common part, comprising a sequence of data members starting from the first data member which is identical from one record of the group to another, wherein steps (a)-(b) continue to be repeated until the number of records remaining in said each group is less than a threshold value, and wherein upon conclusion of step (c) at least some of said information records still remain to be sorted into said desired sequence; and (d) as each group reaches said threshold value, sorting records remaining in the group using a selected one of quicksort and insertsort.
Claim 2
Dependent Claim
251 words
In a computer system, an improved method for sorting a plurality of information records into a desired sequence, some of said information records storing at least two data members, some of the information records storing data members which are not identical from one data member of the record to another, the method comprising: (a) determining for each record a value for the first data member; (b) arranging the records into groups according to the value determined for the first data member of each record, wherein records having an identical value for the first data member are grouped together, and wherein at least some of said information records still remain to be sorted into said desired sequence; (c) further dividing each group into smaller groups by repeating steps (a)-(b) for each one of subsequent data members of each record of each group, so that within any given group all records of the group share a common part said common part, comprising a sequence of data members starting from the first data member which is identical from one record of the group to another, wherein steps (a)-(b) continue to be repeated until the number of records remaining in said each group is less than a threshold value, and wherein upon conclusion of step (c) at least some of said information records still remain to be sorted into said desired sequence; and (d) as each group reaches said threshold value, sorting records remaining in the group using a selected one of quicksort and insertsort.
Claim 3
Dependent Claim
21 words
The method of claim 1, wherein step (d) starts comparisons for sorting at a data member position beyond the common part.
Claim 4
Dependent Claim
26 words
The method of claim 1, wherein step (c) is performed so that steps (a)-(b) are repeated last with a group having the largest number of records.
Claim 5
Dependent Claim
16 words
The method of claim 1, wherein said threshold value is empirically determined for the computer system.
Claim 6
Dependent Claim
14 words
The method of claim 1, wherein said threshold value is equal to about 100.
Claim 7
Dependent Claim
19 words
The method of claim 1, wherein in step (b) the groups themselves are arranged according to the desired sequence.
Claim 8
Dependent Claim
23 words
The method of claim 6, wherein the desired sequence is a selected one of an ascending, a descending, and a user-defined sort order.
Claim 9
Dependent Claim
30 words
The method of claim 7, wherein the desired sequence is an ascending order, and wherein the groups are arranged from a group having lowest-order members to one having highest-order members.
Claim 10
Dependent Claim
30 words
The method of claim 7, wherein the desired sequence is an descending order, and wherein the groups are arranged from a group having highest-order members to one having lowest-order members.
Claim 11
Dependent Claim
14 words
The method of claim 1, wherein said data member includes at least one byte.
Claim 12
Dependent Claim
25 words
The method of claim 1, wherein each said record stores a data structure comprising at least one field for storing at least one data member.
Claim 13
Dependent Claim
26 words
The method of claim 11, wherein each said record includes a plurality of fields, and wherein steps (a)-(d) are performed for selected ones of the fields.
Claim 14
Dependent Claim
18 words
The method of claim 11, wherein data members of a single field are of a common data type.
Claim 15
Dependent Claim
33 words
The method of claim 1, wherein each record is referenced by a pointer stored in a pointer array, and wherein sorting of records is achieved by ordering corresponding pointers in the pointer array.
Claim 16
Dependent Claim
26 words
The method of claim 14, further comprising the step of physically ordering the records according to the order of corresponding pointers stored in the pointer array.
Claim 17
Independent Claim
253 words
A system for sorting a plurality of information records into a desired sequence, the system comprising: (a) a computer having a processor and a memory, said memory for storing the information records, at least some of said information records having at least two data members, and said memory for storing a threshold value; (b) means for determining for each record a value for the first of said at least one data member; (c) means for arranging the records into groups according to the value determined for the first data member of each record, so that records having an identical value for first data members are grouped together in the memory, and wherein each group includes some records which have yet to be ordered into said desired sequence; (d) means for further subdividing the records of each group into additional groups according to values determined for subsequent data members of each record, said means operative on a group until records remaining within a group number less than the threshold value, wherein each group includes some records which have yet to be ordered into said desired sequence, and wherein each record of each group shares a common part with other records of the group, said common part comprising a sequence of data members, starting from the first data member, having identical values from one record of the group to another; and (e) means for sorting records remaining in each group according to said desired sequence, said means employing a selected one of quicksort and insertsort.
Claim 18
Independent Claim
253 words
A system for sorting a plurality of information records into a desired sequence, the system comprising: (a) a computer having a processor and a memory, said memory for storing the information records, at least some of said information records having at least two data members, and said memory for storing a threshold value; (b) means for determining for each record a value for the first of said at least one data member; (c) means for arranging the records into groups according to the value determined for the first data member of each record, so that records having an identical value for first data members are grouped together in the memory, and wherein each group includes some records which have yet to be ordered into said desired sequence; (d) means for further subdividing the records of each group into additional groups according to values determined for subsequent data members of each record, said means operative on a group until records remaining within a group number less than the threshold value, wherein each group includes some records which have yet to be ordered into said desired sequence, and wherein each record of each group shares a common part with other records of the group, said common part comprising a sequence of data members, starting from the first data member, having identical values from one record of the group to another; and (e) means for sorting records remaining in each group according to said desired sequence, said means employing a selected one of quicksort and insertsort.
Claim 19
Dependent Claim
24 words
The system of claim 16, wherein said threshold value is a value empirically determined for said processor and said memory to yield good performance.
Claim 20
Dependent Claim
14 words
The system of claim 16, wherein said threshold value is equal to about 100.
Claim 21
Dependent Claim
34 words
The system of claim 16, wherein said means for determining includes comparison means, coupled to the processor, for comparing the value of said at least one data member within a range of known values.
Claim 22
Dependent Claim
28 words
The system of claim 19, wherein said at least one data member comprises a byte (8 bits) and wherein said range of known values spans 256 possible values.
Claim 23
Dependent Claim
135 words
In a computer system, an improved method for sorting a plurality of information records according to a user-specified order, each said information record for storing a plurality of alphanumeric characters, the method comprising: (a) before sorting the records, scanning successive alphanumeric character positions for each record for dividing the records into subgroups, each said subgroup including only those unsorted records which share a common part with other records of the subgroup, said common part comprising a sequence of identical alphanumeric characters starting from a first alphanumeric character position, each said subgroup being arranged relative to other subgroups according to the user-specified order; and (b) sorting records within each said subgroup with a conventional sort method comprising a selected one of quicksort and insertsort, so that all information records are sorted according to the user-specified order.
Claim 24
Dependent Claim
135 words
In a computer system, an improved method for sorting a plurality of information records according to a user-specified order, each said information record for storing a plurality of alphanumeric characters, the method comprising: (a) before sorting the records, scanning successive alphanumeric character positions for each record for dividing the records into subgroups, each said subgroup including only those unsorted records which share a common part with other records of the subgroup, said common part comprising a sequence of identical alphanumeric characters starting from a first alphanumeric character position, each said subgroup being arranged relative to other subgroups according to the user-specified order; and (b) sorting records within each said subgroup with a conventional sort method comprising a selected one of quicksort and insertsort, so that all information records are sorted according to the user-specified order.
Claim 25
Dependent Claim
30 words
The method of claim 21, wherein in step (b) the conventional sort method is applied starting at an alphanumeric character location beyond the common part for the subgroup being sorted.
References Cited (Backward Citations)
US3611316A
Cited
US4575798A
Cited
US5175803A
Cited
US4809158A
Cited
US5148541A
Cited
US5307265A
Cited
US5072386A
Cited
US5274805A
Cited
US5426779A
Cited
US5551018A
Cited
US5487164A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-03-24 | 2000-09-23 | 2001-03-25 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-03-24 | 2004-09-23 | 2005-03-25 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-03-24 | 2008-09-23 | 2009-03-25 | $7700.00 | Window Closed / Lapsed |