login
Number of comparisons and swaps in the Batcher odd-even merge sort needed to sort n items.
0

%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