cp's OEIS Frontend

A350569 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).

%I A350569 #6 Jan 06 2022 08:16:57
%S A350569 2,18,154,1257,10152,91557,922368,10286658,119281680,1517655690,
%T A350569 20619929376,303487939485,4662169420608
%N A350569 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 A350569 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 A350569 The following table shows the maximum and average number of key comparisons for the original algorithm and for its modified version.
%C A350569        Algorithm H          Modified algorithm
%C A350569 .
%C A350569    n  Worst case           Worst case
%C A350569    |  A350426(n)           A350427(n)
%C A350569    |   |  Average           |   Average
%C A350569    |   |  2*A350428(n)/n!   |   A350569(n)/n!
%C A350569    |   |    |    Average/   |    |    Average/
%C A350569    |   |    |   (n*log(n))  |    |   (n*log(n))
%C A350569    2   1   1.000  0.721     1   1.000  0.721
%C A350569    3   3   3.000  0.910     3   3.000  0.910
%C A350569    4   7   6.500  1.172     7   6.417  1.157
%C A350569    5  12  10.950  1.361    12  10.475  1.302
%C A350569    6  17  15.133  1.408    16  14.100  1.312
%C A350569    7  22  19.789  1.453    20  18.166  1.334
%C A350569    8  29  25.814  1.552    27  22.876  1.375
%C A350569    9  37  32.524  1.645    34  28.347  1.433
%C A350569   10  44  38.631  1.678    39  32.871  1.428
%C A350569   11  51  45.237  1.715    44  38.020  1.441
%C A350569   12  59  51.845  1.739    51  43.048  1.444
%C A350569   13  66  59.021  1.770    57  48.737  1.462
%C A350569   14  73  65.488  1.773    63  53.479  1.447
%C A350569 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 A350569 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 A350569 Cf. A350426, A350427, A350428.
%K A350569 nonn,more
%O A350569 2,1
%A A350569 _Hugo Pfoertner_, Jan 06 2022