The OEIS is supported by the many generous donors to the OEIS Foundation.
%I #6 Jan 06 2022 08:16:57
%S 2,18,154,1257,10152,91557,922368,10286658,119281680,1517655690,
%T 20619929376,303487939485,4662169420608
%N a(n)/n! is the average number of key comparisons required to sort n records with distinct keys using a modified heapsort (Algorithm H in Don Knuth's TAOCP Vol. 3, answer to exercise 18).
%C There are two places in R. W. Floyd's modified algorithm where the keys are compared. The first is in step H4 [Find larger child.] and the second in step H9' [Does K fit?]. The sequence is the sum of the counts of these comparisons, taken over all n! possible orders of the records.
%C The following table shows the maximum and average number of key comparisons for the original algorithm and for its modified version.
%C Algorithm H Modified algorithm
%C .
%C n Worst case Worst case
%C | A350426(n) A350427(n)
%C | | Average | Average
%C | | 2*A350428(n)/n! | A350569(n)/n!
%C | | | Average/ | | Average/
%C | | | (n*log(n)) | | (n*log(n))
%C 2 1 1.000 0.721 1 1.000 0.721
%C 3 3 3.000 0.910 3 3.000 0.910
%C 4 7 6.500 1.172 7 6.417 1.157
%C 5 12 10.950 1.361 12 10.475 1.302
%C 6 17 15.133 1.408 16 14.100 1.312
%C 7 22 19.789 1.453 20 18.166 1.334
%C 8 29 25.814 1.552 27 22.876 1.375
%C 9 37 32.524 1.645 34 28.347 1.433
%C 10 44 38.631 1.678 39 32.871 1.428
%C 11 51 45.237 1.715 44 38.020 1.441
%C 12 59 51.845 1.739 51 43.048 1.444
%C 13 66 59.021 1.770 57 48.737 1.462
%C 14 73 65.488 1.773 63 53.479 1.447
%C This is compatible with Don Knuth's remark, quoted from TAOCP Vol. 3, page 148: Heapsort has the interesting property that its worst case isn't much worse than the average.
%D D. E. Knuth, The Art of Computer Programming Second Edition. Vol. 3, Sorting and Searching. Chapter 5.2.3 Sorting by Selection, Pages 145, 156 and 642. Addison-Wesley, Reading, MA, 1998.
%Y Cf. A350426, A350427, A350428.
%K nonn,more
%O 2,1
%A _Hugo Pfoertner_, Jan 06 2022