Methods and systems for sorting multiplying indexed data

Abstract

The current methods and systems sort three-dimensional data with a reduced number of buffer memories at an increased speed. Based upon the Z-dimension data, the three-dimensional data is sorted in ascending order via two intermediate tables. Since a first intermediate table holds only one set of unique Z values, when there is a recurrence of Z values, a second intermediate table holds these multiply occurring data. At the end, the contents of these intermediate tables are merged into a single result holding table.

What is claimed is: 
     
       1. A method of sorting data sets each having a pair of a unique id and a multiply occurring value, the data sets being sorted in an ascending order based upon the multiply occurring value via a first intermediate table, a second intermediate table and a result table, comprising the steps of: a) initializing the first intermediate table, the second intermediate table and the result table with a predetermined value;   b) placing each data set at a first storage address in the first intermediate table in an ascending order based upon the multiply occurring value, said first storage location being derived from the multiply occurring value, one of the data sets stored at said first storage location defining a stored data set;   c) replacing said stored data set with another of the data sets if the multiply occurring value collides onto said first storage location, said another of the data sets defining a current data set, said stored data set being replaced defining a replaced data set;   d) placing the unique id of said replaced data set at a second storage location in the second intermediate table, said second storage location derived from the unique id of said current data set; and   e) merging the first intermediate table and the second intermediate table into the result table.   
     
     
       2. The method of sorting data sets according to claim 1 wherein said step e) further comprising the steps of: f) transferring said stored data set in the first intermediate table to the result table;   g) transferring said replaced data at the second storage location derived from the unique id of said stored data set which is transferred in said step f); and   h) transferring said replaced data at a third storage location in the second intermediate table, said third storage location being derived from the unique id of said replaced data set which is transferred in said step g).   
     
     
       3. The method of sorting data sets according to claim 2 wherein said steps e) through h) are repeated until said predetermined value is found in the second intermediate table. 
     
     
       4. The method of sorting data sets according to claim 2 wherein the first intermediate table further comprises a second flag for each of said data sets, said second flag indicating an entry of said replaced data at said second storage location in the second intermediate table. 
     
     
       5. The method of sorting data sets according to claim 4 wherein the second intermediate table further comprises a third flag for each of said data sets, said third flag indicating an entry of another of said replaced data set at said third storage location in the second intermediate table. 
     
     
       6. The method of sorting data sets according to claim 1 wherein the first intermediate table has a number of said first storage locations that is equal to a range of the multiply occurring value. 
     
     
       7. The method of sorting data sets according to claim 1 wherein the second intermediate table has a number of said storage locations that is equal to a number of said data sets. 
     
     
       8. The method of sorting data sets according to claim 1 wherein the first intermediate table further comprises a first flag for each of said data sets, said first flag indicating an entry of said stored data set at said first storage location in the first intermediate table. 
     
     
       9. The method of sorting data sets according to claim 1 wherein the unique id is further divided into a predetermined number of portions. 
     
     
       10. The method of sorting data sets according to claim 1 wherein the multiply occurring value is further divided into a predetermined number of portions. 
     
     
       11. A sorting device for sorting input data having a unique data number and a multiply occurring reference value comprising: data number generating means for isolating said unique data numbers for each of said input data;   distribution count memory means having a first memory area in which one of said data numbers is stored at a first address indicated by the corresponding reference value, said one of said data numbers stored in said first memory area defining a stored data number and being replaced with another of said data numbers when said another data number has the same reference value as that of said stored data number, said another data number defining a current data number;   chain memory means a first memory area for storing said stored data number at a second address indicated by said current data number when said stored data number is replaced in said distribution count memory means;   distribution count memory reading means for reading said current data number stored at said first address in said distribution count memory means;   first determining means for determining whether or not said current data number exists at said first address in said distribution count memory means;   resultant memory means for storing said data numbers in a desired sorted condition;   first resultant memory writing means for writing said current data number at a next available address in said resultant memory means in response to said first determining means, said data number just written defining a sorted data number, said predetermined address being inserted;   second determining means for determining whether or not said stored data number exists at said second address having the same reference value indicated by said sorted data number in said chain memory means;   chain memory reading means for reading said stored data number said second address in said chain memory means, said second address of said chain memory means having the same reference value indicated by said stored data number;   second resultant memory writing means for writing the said stored data number at an address adjacent to said next available address in said resultant memory means in response to said second determining means.   
     
     
       12. The sorting device as claimed in claim 11, wherein said distribution count memory means further comprises a second memory area for a first flag for each of said data numbers, said first determining means also further comprising a first flag setting means for setting said first flag when said data number is stored in said distribution count memory means, and a first flag determining means for determining whether or not said first flag is set. 
     
     
       13. The sorting device as claimed in claim 12, wherein said first resultant memory writing means writes said data number located at said first address into said resultant memory means when said first flag is set. 
     
     
       14. The sorting device as claimed in claim 11, wherein said distribution count memory means further comprises a third memory area for a second flag for each of said data numbers, said second determining means also further comprising a second flag setting means for setting said second flag in said distribution count memory means, when the replacement is performed in said distribution count memory means, sand a second flag determining means for determining whether or not said second flat is set. 
     
     
       15. The sorting device as claimed in claim 14, wherein said second resultant memory writing means writes said stored data number located at said second address into said resultant memory means when said second flag is set at said first address of said distribution count memory means. 
     
     
       16. The sorting device as claimed in claim 11, wherein said chain memory means further comprises a second memory area for a third flag for said stored data number, said second determining means further comprising a third flag setting means for setting said third flag in said chain memory means when any data number already exists at an address indicated by a previously stored data number in said chain memory means, and third flag determining means for determining whether or not said third flag is set. 
     
     
       17. The sorting device as claimed in claim 16, wherein said second resultant memory writing means writes said stored data number at an address indicated by said current number in said chain memory when said third flag is set, the data number at said address of said chain memory means into said resultant memory means. 
     
     
       18. The sorting device as claimed in claim 11, further comprising dividing means for dividing data corresponding to said reference value of said input data items into at least two portions comprising less significant portion data and more significant portion data, and said distribution count memory means and said chain memory means divided having portions of respective said first memory area, a number of the portions of each of said first memory area corresponding to a number of the portions into which said reference value data is divided, said distribution count memory means and said chain memory means further having areas in which said less significant portion data is stored. 
     
     
       19. The sorting device as claimed in claim 18, wherein said reference value data comprises 8-bit data, and said dividing means divides said 8-bit data into an upper 5 bits and a lower 3 bits. 
     
     
       20. The sorting device as claimed in claim 18, further comprising flag memory means for storing flag data comprising a plurality of bits each of which corresponds to one address in said distribution count memory means, a corresponding flag bit being set when a data number is written into an area corresponding to a designated address, and wherein said plurality of bits are read as a single flag data item, a flag being detected from the read flag data item, said less significance portion data in said distribution count memory means at the address corresponding to the detected flag being read for the second sorting process. 
     
     
       21. The sorting device as claimed in claim 11, wherein said distribution count memory means and said chain memory means write simultaneously with said data number generating means.