The External Heapsort

Lutz Wegner and Jukka Teuhola
IEEE Trans. on Software Engineering, Vol. 15, No. 7, July 1989, pp. 917-925

Abstract

Heapsort is a well-known 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 random access sorting. Here we show that by replacing key comparisons with merge operations on pages, one obtains an in place external sort which requires O(m log m) page references, where m is the number of pages which the file occupies. The new sort has several useful properties for advanced database management systems. The presentation leads stepwise from the basic algorithm to a refined version which is on par with the merge sort.


Last modified: Mon Jan 16, 1996
Prof. Dr. L. Wegner, Uni GhK - FB 17 - FG DB, e-mail: Wegner@DB.Informatik.Uni-Kassel.DE