The *M-ary tree and *Ternary hillsort

ABSTRACT

Sorting is a significant activity for which better methods are always sought. In many computing scenarios, sorting must be done with the majority of data items remaining on an auxiliary storage device. This paper introduces a new data structure, the *M-ary tree, which improves external sorting. The recent adaptation of the heapsort to an external sorting strategy, called the Hillsort, combined with the *M-ary tree structure allow the development of the *Ternary Hillsort. The *Ternary Hillsort is an external heapsort, which has superior performance over the external heapsort, Hillsort. The *Ternary Hillsort executes faster than Hillsort. The *ternary tree, a variant of a ternary tree, allows the *Ternary Hillsort to exist since parent/child and sibling relationships are easily calculated, as opposed to an ordinary ternary tree.

REFERENCES

• 1: J.W.J. Williams. Algorithm 232 Heamort. Co~mun. ACM 7(6), pp. 347-348 (1964).
• 2: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 3: Alan L. Tharp, File organization and processing, John Wiley & Sons, Inc., New York, NY, 1988
• 4: L.M. Wegner and J.I. Teuhola. The External 925 (1989).
• 5: A. Paulik, Worst-case analysis of a generalized heapsort algorithm, Information Processing Letters, v.36 n.3, p.159-165, Nov. 1990 [doi>10.1016/0020-0190(90)90086-D]
• 6: W.H. Press, et al. Numerical Recioesin C Cambridge University Press, Cambrid

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:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees

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