login
Number of key comparisons to sort all n! permutations of n elements by the optimal trial-pivot quicksort.
13

%I #45 Feb 03 2018 12:54:11

%S 0,0,2,16,112,848,7032,64056,639888,6974928,82531296,1054724256,

%T 14487894144,212971227264

%N Number of key comparisons to sort all n! permutations of n elements by the optimal trial-pivot quicksort.

%C 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.

%H M. Aumüller and M. Dietzfelbinger, <a href="https://doi.org/10.1145/2963102">How Good Is Multi-Pivot Quicksort?</a>, ACM Transactions on Algorithms (TALG), Volume 13 Issue 1, 2016.

%H M. Aumüller and M. Dietzfelbinger, <a href="https://arxiv.org/abs/1510.04676">How Good Is Multi-Pivot Quicksort?</a>, arXiv:1510.04676 [cs.DS], 2016.

%H Daniel Krenn, <a href="https://github.com/dkrenn/quickstar">Quickstar</a>, Program in SageMath, on GitHub.

%H <a href="/index/So#sorting">Index entries for sequences related to sorting</a>.

%Y Cf. A001768, A003070, A036604, A117627, A117628, A159324, A288964, A288965, A288971.

%K nonn,more

%O 0,3

%A _Daniel Krenn_, Jun 20 2017

%E a(9)-a(11) from _Melanie Siebenhofer_, Jan 29 2018

%E a(12)-a(13) from _Melanie Siebenhofer_, Feb 02 2018