Block Sorting of a Large File in External Storage by a 2-Component Key
K. P. Tan, L. S. Hsu · The Computer Journal · 1982
This paper introduces a sorting method (a block sort embedded with another sorting algorithm) to sort a large volume of records in external storage by means of a 2-component numeric key consisting of key 1 and key 2. Based on the value of key 1, the data file is split into many subfiles. Each subfile contains records of common key 1, but with different key 2s. After sorting, all records are linked together by pointers to form a sort file. An index array keeps the list heads to these separate subfiles. The list structure in the file organization facilities updating of the file. This sorting method can be applied to a key of any number of digits. A subroutine of the methodology is illustrated in the Appendix.