

A288970


Number of key comparisons to sort all n! permutations of n elements by the optimal trialpivot quicksort.


11



0, 0, 2, 16, 112, 848, 7032, 64056, 639888, 6974928, 82531296, 1054724256, 14487894144, 212971227264
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

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


LINKS

Table of n, a(n) for n=0..13.
M. AumÃ¼ller and M. Dietzfelbinger, How Good Is MultiPivot Quicksort?, ACM Transactions on Algorithms (TALG), Volume 13 Issue 1, 2016.
M. AumÃ¼ller and M. Dietzfelbinger, How Good Is MultiPivot Quicksort?, arXiv:1510.04676 [cs.DS], 2016.
Daniel Krenn, Quickstar, Program in SageMath, on GitHub.
Index entries for sequences related to sorting.


CROSSREFS

Cf. A001768, A003070, A036604, A117627, A117628, A159324, A288964, A288965, A288971.
Sequence in context: A117627 A117628 A288971 * A037564 A125725 A288965
Adjacent sequences: A288967 A288968 A288969 * A288971 A288972 A288973


KEYWORD

nonn,more


AUTHOR

Daniel Krenn, Jun 20 2017


EXTENSIONS

a(9)a(11) from Melanie Siebenhofer, Jan 29 2018
a(12)a(13) from Melanie Siebenhofer, Feb 02 2018


STATUS

approved



