The Use of Information in Sorting

ABSTRACT

The information-gathering aspect of sorting is considered from a theoretical viewpoint. A large class, R, of sorting algorithms is defined, based on the idea of information use. Properties of this algorithm class are developed, and it is noted that several well-known sorting algorithms are closely related to algorithms in R. The Binary Tree Sort is shown to be in R and to have unique properties in this class. A vector is defined which characterizes the information-gathering efficiency of the algorithms of R. Finally, a more general class of algorithms is defined, and some of the definitions extended to this class. Two intriguing conjectures are given which appear to require graph theory or combinatorial topology for their solution.

REFERENCES

• 1: BEtTS, H.L. The use of information in sorting. Ph.D. thesis (Computing Center Rep. No. 1096), Case Western Reserve U., Cleveland, Ohio, 1967.
• 2: R. C. Bose , R. J. Nelson, A Sorting Problem, Journal of the ACM (JACM), v.9 n.2, p.282-296, April 1962 [doi>10.1145/321119.321126]
• 3: DEMUTH, It. B. Sorting on electronic digital computers. Ph.D. thesis, Stanford U., Stanford, Calif., 1957.
• 4: 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]
• 5: GOLDSTINE, H., AND VON NEUMANN, J. Planning and coding problems for an electronic computing instrument, Pt. I I , Vol. II. Institute for Advanced Study, Princeton, N.J.. 1948.
• 6: Thomas N. Hibbard, Some Combinatorial Properties of Certain Trees With Applications to Searching and Sorting, Journal of the ACM (JACM), v.9 n.1, p.13-28, Jan. 1962 [doi>10.1145/321105.321108]
• 7: LYNCH, W. C. More combinatorial properties of certain trees. Comput. J. 7 (1965), 299- 302.
• 8: MAUCHLY, J.W. Sorting and collating. In "Theory and techniques for the design of electronic digital computers," Moore School Lectures, U. of Pennsylvania, Philadelphia, Pa.. 1948.
• 9: TUR~_N, P. On the theory of graphs. Colloq. Math. 3 (1954), 19-30 (Inst. of Math., Polish Acad. of Sci., Warsaw, Poland).

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Measurement, Performance, Theory, Verification