Snip

Heapsort is an internal sorting method which sorts an ar... place in O(n log n) time. Heapsort is generally consider... external randomaccess sorting. By replacing key compari... operations on pages, it is shown how to obtain an inpla... which requi


Categories 


For Snip 
loading snip actions ... 

For Page 
loading url actions ... 
HTML 
Heapsort is an internal sorting method which sorts an array of n records in place in O(n log n) time. Heapsort is generally considered unsuitable for external randomaccess sorting. By replacing key comparisons with merge operations on pages, it is shown how to obtain an inplace external sort which requires O(m log m) page references, where m is the number of pages which the file occupies. The new sort method (called Hillsort) has several useful properties for advanced database management systems. Not only does Hillsort operate in place, i.e., no additional external storage space is required assuming that the page table can be kept in core memory, but accesses to adjacent pages in the heap require one seek only if the pages are physically contiguous. The authors define the Hillsort model of computation for external randomaccess sorting, develop the complete algorithm and then prove it correct. The model is next refined and a buffer management concept is introduced so as to reduce the number of merge operations and page references, and make the method competitive to a basic balanced twoway external merge. Performance characteristics are noted such as the worstcase upper bound, which can be carried over from Heapsort, and the averagecase behavior, deduced from experimental findings. It is shown that the refined version of the algorithm which is on a par with the external merge sort. 
