A001768 -id:A001768 - cp's OEIS frontend

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

0, 0, 2, 16, 112, 848, 7032, 64056, 639888, 6974928, 82531296, 1054724256, 14487894144, 212971227264

Offset: 0

Daniel Krenn, Jun 20 2017

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.

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.

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

a(9)-a(11) from Melanie Siebenhofer, Jan 29 2018

a(12)-a(13) from Melanie Siebenhofer, Feb 02 2018

A036604 Sorting numbers: minimal number of comparisons needed to sort n elements.

Original entry on oeis.org

0, 1, 3, 5, 7, 10, 13, 16, 19, 22, 26, 30, 34, 38, 42, 46, 50, 54, 58, 62, 66, 71

Offset: 1

N. J. A. Sloane

The Peczarski paper in Algorithmica has a table giving upper and lower bounds that differ by at most 1. In particular, the values a(20) = 62 and a(21) = 66 are also known. - Bodo Manthey, Mar 01 2007

D. E. Knuth, Art of Computer Programming, Vol. 3, 2nd. edition, Sect. 5.3.1.
E. Reingold, J. Nievergelt and N. Deo, Combinatorial Algorithms, Prentice-Hall, 1977, section 7.4, p. 309.
Tianxing Tao, On optimal arrangement of 12 points, pp. 229-234 in Combinatorics, Computing and Complexity, ed. D. Du and G. Hu, Kluwer, 1989. [Finds a(12).]

Eisa Alanazi, Malek Mouhoub, Sandra Zilles, Interactive Learning of Acyclic Conditional Preference Networks, arXiv:1801.03968 [cs.AI], 2018.
Enrico Iurlano and Günther R. Raidl, SAT-Based Search for Minwise Independent Families, arXiv:2412.11811 [cs.DM], 2024. See p. 5.
Marcin Peczarski, New Results in Minimum-Comparison Sorting, Algorithmica 40(2):133-145, 2004.
Marcin Peczarski, The Ford-Johnson algorithm still unbeaten for less than 47 elements, Information Processing Letters, Volume 101, Issue 3, 14 February 2007, Pages 126-128.
Marcin Peczarski, Towards optimal sorting of 16 elements, arXiv:1108.0866 [cs.DS], 2011.
Marcin Peczarski, Sorting 13 Elements Requires 34 Comparisons, Proc. of the 10th European Symp. on Algorithms (ESA), vol. 2452 of Lecture Notes in Comput. Sci., pp. 785-794. Springer, 2002.
Florian Stober and Armin Weiss, Lower bounds for sorting 16, 17, and 18 elements, 2023 Proc. Symp. Algorithm Engineering and Experiments pp. 201-213, 2023. SIAM; arXiv preprint, arXiv:2206.05597 [cs.DS], 2022.
Index entries for sequences related to sorting

A001768 is an upper bound, A003070 a lower bound.

Cf. A360495.

a(13) was determined by Marcin Peczarski. - Bodo Manthey, Sep 25 2002
a(14)=38 and a(22)=71 were determined by Marcin Peczarski. - Bodo Manthey (manthey(AT)cs.uni-sb.de), Feb 28 2007
a(16)=46, a(17)=50, and a(18)=54 were determined by Stober and Weiss. - Robert McLachlan, May 29 2024
a(19)-a(22) from table in arXiv preprint of Stober and Weiss. - Domotor Palvolgyi, Jun 03 2025

A350567 a(n) is the maximum number of key comparisons required to perform an indirect sort of n records with distinct keys using a two-way merge (A. D. Woodall's mergesort).

Original entry on oeis.org

1, 4, 6, 10, 13, 17, 20, 25, 29, 34, 38, 43, 47, 52

Offset: 2

Hugo Pfoertner, Jan 09 2022

There are six places in the Algol 60 procedure mergesort where the keys are compared. The sequence shows the maxima of the counts of these comparisons, determined over all n! possible orders of the records.

a(16) >= 56.

D. E. Knuth, The Art of Computer Programming Second Edition. Vol. 3, Sorting and Searching. Chapter 5.2.4 Sorting by Merging, Pages 164-166. Addison-Wesley, Reading, MA, 1998.

A. D. Woodall, An internal sorting procedure using a two-way merge, Algorithm 45, The Computer Journal, Volume 13, Number 1, February 1970, Algorithms Supplement, pp. 110-111.

A350568 provides the corresponding average numbers and a comparison table.

Cf. A001768, A001855, A350569.

A350568 a(n)/n! is the average number of key comparisons required to perform an indirect sort of n records with distinct keys using a two-way merge (A. D. Woodall's mergesort).

Original entry on oeis.org

2, 19, 130, 992, 8145, 73665, 725630, 7840280, 92297011, 1176802235, 16129154724, 236335661166, 3685509077329, 60981635041557

Offset: 2

Hugo Pfoertner, Jan 09 2022

There are six places in the Algol 60 procedure mergesort where the keys are compared. The sequence is the sum of the counts of these comparisons, taken over all n! possible orders of the records.
The following table shows the maximum and average number of key comparisons.
.
   n  Worst case
   |  A350567(n)
   |   |  Average
   |   |  a(n)/n!
   |   |    |    Average/
   |   |    |   (n*log(n))
   2   1   1.000  0.721
   3   4   3.167  0.961
   4   6   5.417  0.977
   5  10   8.267  1.027
   6  13  11.313  1.052
   7  17  14.616  1.073
   8  20  17.997  1.082
   9  25  21.606  1.093
  10  29  25.435  1.105
  11  34  29.481  1.118
  12  38  33.672  1.129
  13  43  37.953  1.138
  14  47  42.276  1.144
  15  52  46.634  1.148

D. E. Knuth, The Art of Computer Programming Second Edition. Vol. 3, Sorting and Searching. Chapter 5.2.4 Sorting by Merging, Pages 164-166. Addison-Wesley, Reading, MA, 1998.

A. D. Woodall, An internal sorting procedure using a two-way merge, Algorithm 45, The Computer Journal, Volume 13, Number 1, February 1970, Algorithms Supplement, pp. 110-111.

Cf. A001768, A001855, A350567, A350569.

A123533 Primes in A001855.

Original entry on oeis.org

3, 5, 11, 17, 29, 37, 41, 59, 79, 89, 109, 349, 419, 433, 461, 503, 587, 601, 643, 727, 769, 809, 857, 881, 929, 937, 953, 977, 1009, 1033, 1049, 1097, 1129, 1153, 1193, 1201, 1217, 1249, 1289, 1297, 1321, 1361, 1409, 1433, 1481, 1489, 1553, 1601, 1609

Offset: 1

Jonathan Vos Post, Nov 10 2006

Paolo Xausa, Table of n, a(n) for n = 1..10000

Intersection of A000040 and A001855.

Cf. A001768, A029837, A003071, A000337, A030190, A030308, A061168.

A001855 := proc(n) local c ; c := ceil(log[2](n)) ; n*c-2^c+1 ; end: for n from 1 to 300 do srts := A001855(n) : if isprime(srts) then printf("%d, ",srts) ; fi ; od : # R. J. Mathar, Dec 16 2006

Select[Accumulate[BitLength[Range[0, 300]]], PrimeQ] (* Paolo Xausa, Jun 28 2024 *)

Corrected and extended by R. J. Mathar, Dec 16 2006

A123535 Recurrence from values at floor of a third and two-thirds.

Original entry on oeis.org

1, 4, 8, 16, 17, 26, 32, 33, 43, 58, 59, 61, 73, 74, 90, 101, 102, 105, 124, 125, 127, 145, 146, 158, 170, 171, 175, 210, 211, 213, 217, 218, 237, 241, 242, 255, 280, 281, 283, 289, 290, 326, 344, 345, 348, 364, 365, 367, 388, 389, 394, 399, 400, 414, 459, 460

Offset: 0

Jonathan Vos Post, Nov 11 2006

Roughly analogous to maximal number of comparisons for sorting n elements by binary insertion (A001855).

			a(0) = 1 by definition.
a(1) = a(floor(1/3)) + a(floor(2/3)) + 1 + 1 = a(0) + a(0) + 2 = 4.
a(2) = a(floor(2/3)) + a(floor(4/3)) + 2 + 1 = a(0) + a(1) + 3 = 8.
a(3) = a(floor(3/3)) + a(floor(6/3)) + 3 + 1 = a(1) + a(2) + 4 = 16.
a(4) = a(floor(4/3)) + a(floor(8/3)) + 4 + 1 = a(1) + a(2) + 5 = 17.
a(5) = a(floor(5/3)) + a(floor(10/3)) + 5 + 1 = a(1) + a(3) + 6 = 26.
a(6) = a(floor(6/3)) + a(floor(12/3)) + 6 + 1 = a(2) + a(4) + 7 = 32.

Paolo Xausa, Table of n, a(n) for n = 0..10000
Wikipedia, Akra-Bazzi method.

Cf. A001768, A001855, A029837, A003071, A000337, A030190, A030308, A061168.

A123535 := proc(n) options remember ; if n = 0 then RETURN(1) ; else RETURN(A123535(floor(n/3))+A123535(floor(2*n/3))+n+1) ; fi ; end: for n from 0 to 100 do printf("%d,",A123535(n)) ; od : # R. J. Mathar, Jan 13 2007

a[0] = 1; a[n_] := a[n] = a[Floor[n/3]] + a[Floor[2*n/3]] + n + 1;
Array[a, 100, 0] (* Paolo Xausa, Jun 27 2024 *)

a(0) = 1, for n>0: a(n) = a(floor(n/3)) + a(floor(2n/3)) + n + 1.

Corrected and extended by R. J. Mathar, Jan 13 2007

a(0)=1 prepended by Paolo Xausa, Jun 27 2024

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A036604 Sorting numbers: minimal number of comparisons needed to sort n elements.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A350567 a(n) is the maximum number of key comparisons required to perform an indirect sort of n records with distinct keys using a two-way merge (A. D. Woodall's mergesort).

Views

Author

Keywords

Comments

References

Links

Crossrefs

A350568 a(n)/n! is the average number of key comparisons required to perform an indirect sort of n records with distinct keys using a two-way merge (A. D. Woodall's mergesort).

Views

Author

Keywords

Comments

References

Links

Crossrefs

A123533 Primes in A001855.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A123535 Recurrence from values at floor of a third and two-thirds.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions