experiments have shown that the performance of heapsort is extremely consistenton average it uses only slightly fewer comparisons than the worst-case bound suggests for many yearsnobody had been able to show nontrivial bounds on heapsort' average running time the problemit seemsis that successive deletemax operations destroy the heap' randomnessmaking the probability arguments very complex eventuallyanother approach proved successful theorem the average number of comparisons used to heapsort random permutation of distinct items is log ( log log nproof the heap construction phase uses (ncomparisons on averageand so we only need to prove the bound for the second phase we assume permutation of { nsuppose the ith deletemax pushes the root element down di levels then it uses di comparisons for heapsort on any inputthere is cost sequence dn that defines the cost of phase that cost is given by md = di the number of comparisons used is thus md let (nbe the number of heaps of items one can show (exercise that ( ( /( )) (where we will show that only an exponentially small fraction of these heaps (in particular ( / ) have cost smaller than (log log log when this is shownit follows that the average value of md is at least minus term that is ( )and thus the average number of comparisons is at least consequentlyour basic goal is to show that there are very few heaps that have small cost sequences because level di has at most di nodesthere are di possible places that the root element can go for any di consequentlyfor any sequence dthe number of distinct corresponding deletemax sequences is at most sd dn simple algebraic manipulation shows that for given sequence ds md because each di can assume any value between and log there are at most (log ) possible sequences it follows that the number of distinct deletemax sequences that require cost exactly equal to is at most the number of cost sequences of total cost times the number of deletemax sequences for each of these cost sequences bound of (log ) follows immediately the total number of heaps with cost sequence less than is at most - (log ) (log ) =