cp's OEIS Frontend

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

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