A lower bound for the worst case of bottom-up-heapsort

Abstract

Bottom-Up-Heapsort ia a variant of Heapsort. Till now, its worst case complexity or the number of comparisons is known to be bounded above by 1.5nlog n+O(n), where n is the number of elements to be sorted; but it was conjectured to be nlog n+O(n). In this paper we give a construction that proves an asymptotic lower bound of 1.25nlog n-O(nlog log n) comparisons for the worst case.