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

0, 1, 3, 5, 9, 12, 16, 19, 28, 32, 38, 42, 48, 53, 59, 63, 85, 90, 98, 103, 112, 119, 127, 132, 140, 147, 156, 162, 171, 178, 186, 191, 246, 252, 262, 268, 280, 289, 299, 305, 317, 327, 339, 347, 359, 368, 378, 384, 394, 403, 415, 423, 436, 446, 457, 464, 476, 486, 498, 506

Offset: 1

Author

Darío Clavijo, Aug 22 2024

Keywords

• nonn

Links

• Wikipedia, Batcher odd even merge sort

Crossrefs

Cf. A000079, A350567.

Programs

Python

def a(n):
    p,c = 1,0
    while p < n:
        p2, k = p << 1, p
        while k >= 1:
            for j in range(k % p, n - k, k << 1):
                for i in range(min(k, n - j - k)):
                    ij = i+j
                    if ij // p2 == (ij + k) // p2: c += 1
            k >>= 1
        p <<= 1
    return c
print([a(n) for n in range(1, 61)])