login/register

Snip!t from collection of Alan Dix

see all channels for Alan Dix

Snip
summary

Sorting is a significant activity for which better metho... sought. In many computing scenarios, sorting must be don... majority of data items remaining on an auxiliary storage... paper introduces a new data structure, the *M-ary tree, ... external so

The *M-ary tree and *Ternary hillsort
http://portal.acm.org/citation.cfm?id=131220&coll=portal&dl=ACM

Categories

/Channels/AVL trees

[ go to category ]

For Snip

loading snip actions ...

For Page

loading url actions ...

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.

HTML

<div class="abstract"><p class="abstract"><par>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.</par> </p> </div>