A350426 a(n) is the maximum number of key comparisons required to sort n records with distinct keys using heapsort (Algorithm H in Don Knuth's TAOCP Vol. 3).

1, 3, 7, 12, 17, 22, 29, 37, 44, 51, 59, 66, 73, 80

Offset

2,2

Comments

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 shows the maxima of the counts of these comparisons, determined over all n! possible orders of the records.

a(16) >= 90.

References

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.

Links

Table of n, a(n) for n=2..15.

Crossrefs

Cf. A350427, A350428.

A350569 contains a table with the maximum and average number of comparisons for the original algorithm and for its modified version.

Sequence in context: A192740 A310246 A310247 * A332263 A376998 A310248

Adjacent sequences: A350423 A350424 A350425 * A350427 A350428 A350429

Keyword

nonn,more

Author

Hugo Pfoertner, Jan 05 2022

Status

approved