Patent ID: 8001134

Claim:
A method for performing the string generation phase of a sort merge process in a computer, upon data in a first file comprising data blocks in a sortin file residing in persistent machine-readable storage, wherein said data may contain presorted portions, said method comprising: (a) reading a portion of the sortin file into a first machine-readable memory area and noting in a second machine-readable memory area the locations on said persistent machine-readable storage from which the blocks of said portion were read; (b) determining the location of any presorted runs existing in said read portion; (c) marking as free the memory locations in said first memory area that are occupied by said presorted runs and noting in said second machine-readable memory area the locations in said persistent machine-readable storage from which the blocks of said presorted portions had been read; (d) repeating the preceding three steps until either all data in the sortin file has been read or until said first memory area is full, and then sorting any data remaining in said first memory area, writing said sorted data to said persistent machine-readable storage, and noting in said second machine-readable memory area the locations in said persistent machine-readable storage area of said sorted data that was so written; and (e) writing a file directory structure for a second file in persistent machine-readable storage, incorporating therein said locations of the blocks of said presorted runs and the locations of the blocks of said sorted data.