A006282 Sorting numbers: number of comparisons in Batcher's parallel sort.
0, 1, 3, 5, 9, 12, 16, 19, 26, 31, 37, 41, 48, 53, 59, 63, 74, 82, 91, 97, 107, 114, 122, 127, 138, 146, 155, 161, 171, 178, 186, 191, 207, 219, 232, 241, 255, 265, 276, 283, 298, 309, 321, 329, 342, 351, 361, 367, 383, 395, 408, 417, 431, 441, 452, 459, 474
Offset: 1
Examples
G.f. = x^2 + 3*x^3 + 5*x^4 + 9*x^5 + 12*x^6 + 16*x^7 + 19*x^8 + 26*x^9 + 31*x^10 + ...
References
- R. W. Floyd and D. E. Knuth, The Bose-Nelson sorting problem, pp. 163-172 of J. N. Srivastava, ed., A Survey of Combinatorial Theory, North-Holland, 1973.
- D. E. Knuth, Art of Computer Programming, Vol. 3, Sect. 5.3.4, Eq. (10).
- N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Links
- T. D. Noe, Table of n, a(n) for n = 1..1000
- J.-P. Allouche and Jeffrey Shallit, The ring of k-regular sequences, preprint.
- J.-P. Allouche and Jeffrey Shallit, The ring of k-regular sequences, Theoretical Computer Sci., Vol. 98 (1992), pp. 163-197.
- Index entries for sequences related to sorting
Programs
-
Mathematica
c[m_, n_] /; m*n <= 1 = m*n; c[m_, n_] := c[m, n] = c[ Ceiling[m/2], Ceiling[n/2] ] + c[ Floor[m/2], Floor[n/2] ] + Floor[(m + n - 1)/2]; a[1] = 0; a[n_] := a[n] = a[ Ceiling[n/2] ] + a[ Floor[n/2] ] + c[ Ceiling[n/2], Floor[n/2] ]; Table[ a[n], {n, 1, 57}] (* Jean-François Alcover, Jan 19 2012, from formula *) -
PARI
(c(m, n) = local(i, j); i=ceil(m/2); j=ceil(n/2); if( m*n<2, m*n, c(i, j) + c(m\2, n\2) + (m+n-1)\2)); {a(n) = local(i, j); i=ceil(n/2); j=floor(n/2); if( n<2, 0, a(i) + a(j) + c(i, j))}; /* Michael Somos, Feb 07 2004 */
Formula
a(1)=0, a(n) = a(ceiling(n/2)) + a(floor(n/2)) + C(ceiling(n/2), floor(n/2)), n > 1, where the C function is defined in Knuth by C(m,n) = m*n if m*n <= 1 and C(m,n) = C(ceiling(m/2),ceiling(n/2)) + C(floor(m/2),floor(n/2)) + floor((m+n-1)/2) otherwise.