Method for sorting data in a computer at high speed by using data word values for address locations

Claim 1

Digital data processor apparatus for sorting a plurality of unsorted data words into sequential order, said digital data processor comprising: A. at least four storage table means--referred to as first storage table means, second storage table means, third storage table means, and fourth storage table means, respectively--each capable of storing a plurality of data words at addressable locations therein, B. address-forming means for generating an address for each of successive candidate ones of said unsorted data words, where each such data word has a value that can be represented by a plurality of digits arranged in order of increasing significance, and where each such address is generated by shifting the digits representing the value of the corresponding data word to remove therefrom one or more digits of least significance, C. primary sort means, coupled to said address-forming means, for testing said first storage table means at a location corresponding to the address of a candidate data word to determine whether that location is occupied by at least one prior data word, said primary sort means including means for responding to a negative such determination for storing that candidate data word in said first storage table means at that location, said primary sort means further including means for responding to a positive such determination for (i) storing said candidate data word and said at least one prior data word in said second storage table means at a next available addressable location therein, and (ii) storing in said first storage table, at said location corresponding to the address of the candidate data word, a signal representative of that next available addressable location, D. merge/gathering means, coupled to said at least four storage table means, for determining whether a remaining storage capacity in said second storage table means is sufficient and, if not, for storing in a selected, alternating one of said third storage table and said fourth storage table means a sorted list of data words formed by merging data words stored in the others of said storage table means, and for clearing said others of said storage table means to permit storage therein of further data words.