The heap-mergesort

In this paper, we present a new mergesort algorithm which can sort n(= 2(h1) - 1) elements using no more than n log(2)(n + 1) - (13/12)n - 1 element comparisons in the worst case. This algorithm includes the heap (fine heap) creation phase as a pre-processing step, and for each internal node upsilo n, its left, and right subheaps are merged into a sorted list of the elemen ts under that node. Experimental results show that this algorithm requires only n log(2) (n + 1) - 1.2n element comparisons in the average case. Brit it requires extra space for n LINK fields. (C) 2000 Elsevier Science Ltd. A ll rights reserved.