The *M-ary tree and *Ternary hillsort
Fred L. Heller, Alan L. Tharp · 1992
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.