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

%I #23 Feb 05 2018 10:29:56

%S 0,0,2,16,112,848,7008,63648,635040,6915168,81757440,1044161280,

%T 14334076800,210595524480

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

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

%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. A288964, A288965, A288970.

%K nonn,more

%O 0,3

%A _Daniel Krenn_, Jun 20 2017

%E a(9)-a(13) from _Melanie Siebenhofer_, Feb 05 2018