Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%I #6 Jan 06 2022 08:17:04
%S 1,9,78,657,5448,49869,520416,5901138,70092000,902850273,12416814432,
%T 183763314090,2854581512832
%N 2*a(n)/n! is the average number of key comparisons required to sort n records with distinct keys using heapsort (Algorithm H in Don Knuth's TAOCP Vol. 3)
%C There are two places in the algorithm where the keys are compared. The first is in step H4 [Find larger child.] and the second in step H6 [Larger than K?]. The sequence is the sum, divided by 2, of the counts of these comparisons, taken over all n! possible orders of the records.
%D D. E. Knuth, The Art of Computer Programming Second Edition. Vol. 3, Sorting and Searching. Chapter 5.2.3 Sorting by Selection, Page 145. Addison-Wesley, Reading, MA, 1998.
%Y Cf. A350426, A350427.
%Y A350569 contains a table with the maximum and average number of comparisons for the original algorithm and for its modified version.
%K nonn,more
%O 2,2
%A _Hugo Pfoertner_, Jan 05 2022