%I #7 Aug 23 2024 10:16:23
%S 0,1,3,5,9,12,16,19,28,32,38,42,48,53,59,63,85,90,98,103,112,119,127,
%T 132,140,147,156,162,171,178,186,191,246,252,262,268,280,289,299,305,
%U 317,327,339,347,359,368,378,384,394,403,415,423,436,446,457,464,476,486,498,506
%N Number of comparisons and swaps in the Batcher odd-even merge sort needed to sort n items.
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Batcher_odd%E2%80%93even_mergesort">Batcher odd even merge sort</a>
%o (Python)
%o def a(n):
%o p,c = 1,0
%o while p < n:
%o p2, k = p << 1, p
%o while k >= 1:
%o for j in range(k % p, n - k, k << 1):
%o for i in range(min(k, n - j - k)):
%o ij = i+j
%o if ij // p2 == (ij + k) // p2: c += 1
%o k >>= 1
%o p <<= 1
%o return c
%o print([a(n) for n in range(1, 61)])
%Y Cf. A000079, A350567.
%K nonn
%O 1,3
%A _DarĂo Clavijo_, Aug 22 2024