A288971 Number of key comparisons to sort all n! permutations of n elements by the optimal quadral-pivot quicksort.

0, 0, 2, 16, 112, 848, 7008, 63648, 635040, 6915168, 81757440, 1044161280, 14334076800, 210595524480

Offset: 0

Author

Daniel Krenn, Jun 20 2017

Keywords

• nonn
• more

Comments

The 4 pivot elements are chosen from fixed indices (e.g. the last 4 elements). The "optimal" strategy minimizes, after the choice of the pivots is done, the expected partitioning cost.

Links

• M. Aumüller and M. Dietzfelbinger, How Good Is Multi-Pivot Quicksort?, ACM Transactions on Algorithms (TALG), Volume 13 Issue 1, 2016.
• M. Aumüller and M. Dietzfelbinger, How Good Is Multi-Pivot Quicksort?, arXiv:1510.04676 [cs.DS], 2016.
• Daniel Krenn, Quickstar, Program in SageMath, on GitHub.
• Index entries for sequences related to sorting.

Crossrefs

Cf. A288964, A288965, A288970.

Extensions

a(9)-a(13) from Melanie Siebenhofer, Feb 05 2018