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

2, 18, 154, 1257, 10152, 91557, 922368, 10286658, 119281680, 1517655690, 20619929376, 303487939485, 4662169420608

Offset: 2

Author

Hugo Pfoertner, Jan 06 2022

Keywords

• nonn
• more

Comments

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.

The following table shows the maximum and average number of key comparisons for the original algorithm and for its modified version.

Algorithm H Modified algorithm

.

n Worst case Worst case

| A350426(n) A350427(n)

| | Average | Average

| | 2*A350428(n)/n! | A350569(n)/n!

| | | Average/ | | Average/

| | | (n*log(n)) | | (n*log(n))

2 1 1.000 0.721 1 1.000 0.721

3 3 3.000 0.910 3 3.000 0.910

4 7 6.500 1.172 7 6.417 1.157

5 12 10.950 1.361 12 10.475 1.302

6 17 15.133 1.408 16 14.100 1.312

7 22 19.789 1.453 20 18.166 1.334

8 29 25.814 1.552 27 22.876 1.375

9 37 32.524 1.645 34 28.347 1.433

10 44 38.631 1.678 39 32.871 1.428

11 51 45.237 1.715 44 38.020 1.441

12 59 51.845 1.739 51 43.048 1.444

13 66 59.021 1.770 57 48.737 1.462

14 73 65.488 1.773 63 53.479 1.447

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.

References

• 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.

Crossrefs

Cf. A350426, A350427, A350428.