Samplesort: A Sampling Approach to Minimal Storage Tree Sorting

ABSTRACT

The methods currently in use and previously proposed for the choice of a root in minimal storage tree sorting are in reality methods for making inefficient statistical estimates of the median of the sequence to be sorted. By making efficient use of the information in a random sample chosen during input of the sequence to be sorted, significant improvements over ordinary minimal storage tree sorting can be made. A procedure is proposed which is a generalization of minimal storage tree sorting and which has the following three properties: (a) There is a significant improvement (over ordinary minimal storage tree sorting) in the expected number of comparisons required to sort the input sequence. (b) The procedure is statistically insensitive to bias in the input sequence. (c) The expected number of comparisons required by the procedure approaches (slowly) the information-theoretic lower bound on the number of comparisons required. The procedure is, therefore, “asymptotically optimal.”

REFERENCES

• 1: BELL, D.A. The principles of sorting. Computer J . 1, 1 (1958), 71-77.
• 2: C. C. Gotlieb, Sorting on computers, Communications of the ACM, v.6 n.5, p.194-201, May 1963 [doi>10.1145/366552.366555]
• 3: R. M. Frank , R. B. Lazarus, A high-speed sorting procedure, Communications of the ACM, v.3 n.1, p.20-22, Jan. 1960 [doi>10.1145/366947.366957]
• 4: 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]
• 5: Thomas N. Hibbard, An empirical study of minimal storage sorting, Communications of the ACM, v.6 n.5, p.206-213, May 1963 [doi>10.1145/366552.366557]
• 6: HOARE, C. A.R. Quicksort. Computer J. 5 (1962), 10-15.
• 7: KNUTH, D .E . Personal communication.
• 8: MORRIS, R. Some theorems on sorting. SIAM J. Appl. Math. 17, 1 (Jan. 1969), 1-6.
• 9: D. L. Shell, A high-speed sorting procedure, Communications of the ACM, v.2 n.7, p.30-32, July 1959 [doi>10.1145/368370.368387]
• 10: SIEGEL, S. Nonparametric Statistics. McGraw-Hill, New York, 1956. 11. WINDLEY, P .F . Trees, forests and rearranging. Computer J . 3, 2 (1960), 84-88.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS

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