Distribution-based replacement selection sorting system
US5487164A · kind A · utility
Assignee
Inventors
Key dates
| Filing date | Sep 14, 1993 |
| Grant date | Jan 23, 1996 |
| Priority date | — |
| Expiry date | Sep 14, 2013 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F2207/224
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
An external data record sorting system that adaptively combines elements of both the distribution-based and the comparison-based sort procedures. The internal distribution-based sorting procedure generates sorted record strings that are twice as long on average as the available internal memory storage space. This MSB radix distribution procedure is adaptively optimized to data file characteristics by a predetermined threshold test that halts the distribution pass for a bin containing fewer records than a predetermined threshold number, which are then immediately sorted using a simpler comparison-based sorting procedure. This system also overlaps the input file reads and secondary storage writes between distribution sequences, thereby minimizing the non-overlapping portions of input/output operations and internal processing operations. As sorted records are written to secondary storage and new records are moved from the input file, the new records may be added to the current distributive sort tree, thereby minimizing the total number of strings created. Because new records are moved in from the input file concurrently with the removal of sorted records to the output area, the averag…
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.