Sorting using heap structure

Abstract

In this paper we present a new sorting algorithm for heaps which can sort n (=2 ^h+1 – 1) elements using no more than nlog₂(n+1) – (13/12)n – 1 element comparisons in the worst case 2 (including the heap creation phase). Experimental results show that this algorithm requires only nlog₂(n+1) – 1.2n element comparisons in the average case. However it requires extra space for 2 n LINK fields

Keywords:

• Heapsort
• MDR-HEAPSORT
• Mergesort
• Complexity
• Fine heap

C.R. Category::

• F.2.2