Boots – shoes – and leggings
Patent
1993-09-14
1996-01-23
Kulik, Paul V.
Boots, shoes, and leggings
364DIG1, 3642229, 3642821, 3642832, G06F 736
Patent
active
054871646
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 average output string can be twice the size of internal storage. By minimizing the number of strings that are later merged to complete the sort, overall external sorting procedure time is minimized.
REFERENCES:
patent: 4210961 (1980-07-01), Whitlow et al.
patent: 4575798 (1986-03-01), Lindstrom et al.
patent: 4809158 (1989-02-01), McCauley
patent: 5396622 (1995-03-01), Lee et al.
Nagler, H., "Amphisbaenic Sorting", Journal of the ACM, Oct. 1959, pp. 459-468.
Knuth, Donald E., "The Art of Computer Programming--Volume 3/Sorting and Searching", 1973 by Addison-Wesley Publishing Co., pp. 170-180, 347-360.
Friend, E. H., "Sorting on Electronic Computer Systems", Journal of the ACM, vol. 3, No. 3, Jul. 1956, pp. 134-168.
Kirchhofer Richard
Wagar Bruce A.
International Business Machines - Corporation
Kulik Paul V.
LandOfFree
Distribution-based replacement selection sorting system does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Distribution-based replacement selection sorting system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Distribution-based replacement selection sorting system will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1510984