Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

It is currently far from uncommon for researchers to be confronted with the problem of sorting large files of data, e.g., 20,000 items or keys. One sorting procedure, known as address calculation sorting, is a two stage process in which an address calculation function is constructed by a preliminary examination of the keys. This function is used to insert each key into a location, hopefully near its position in the final sorted file. This process has been referred to as “rough focusing.” In the second phase the tentatively inserted key is compared to its neighbors to assure that it has been inserted correctly in relation to previously processed keys. This is referred to as “fine focusing.” It is currently far from uncommon for researchers to be confronted with the problem of sorting large files of data, e.g., 20,000 items or keys. One sorting procedure, known as address calculation sorting, is a two stage process in which an address calculation function is constructed by a preliminary examination of the keys. This function is used to insert each key into a location, hopefully near its position in the final sorted file. This process has been referred to as “rough focusing.” In the second phase the tentatively inserted key is compared to its neighbors to assure that it has been inserted correctly in relation to previously processed keys. This is referred to as “fine focusing.”

REFERENCES

• 1: N I AKHIEZER Theory, of approximation Ungar New York 1956
• 2: Ivan Flores, Analysis of Internal Computer Sorting, Journal of the ACM (JACM), v.8 n.1, p.41-80, Jan. 1961 [doi>10.1145/321052.321055]
• 3: Ivan Flores, Computer Time for Address Calculation Sorting, Journal of the ACM (JACM), v.7 n.4, p.389-409, Oct. 1960 [doi>10.1145/321043.321051]
• 4: C. C. Gotlieb, Sorting on computers, Communications of the ACM, v.6 n.5, p.194-201, May 1963 [doi>10.1145/366552.366555]
• 5: E. J. Isaac , R. C. Singleton, Sorting by Address Calculation, Journal of the ACM (JACM), v.3 n.3, p.169-174, July 1956 [doi>10.1145/320831.320834]
• 6: B. F. Cheydleur , R. Kronmal , M. Tarter, Analysis of computational systems: Cumulative polygon address calculation sorting, Proceedings of the 1965 20th national conference, p.376-385, August 24-26, 1965, Cleveland, Ohio, United States [doi>10.1145/800197.806060]
• 7: R A KRONMAL M E TARTER Address calculation sorting with minimal storage requirement Submitted for publication to the J ACM
• 8: F J MASSEY The Kolmogorov-Smirnov test for goodness of fit Journal of American Statistical Association 46:68-78 March 1951
• 9: J F STEFFENSEN Interpolation Chelsea New York 1950

INDEX TERMS

Primary Classification:
  E. Data
  E.5 FILES
      Subjects: Sorting/searching

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Distribution functions

General Terms:
Algorithms, Theory