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,3

Links

Table of n, a(n) for n=1..60.

Wikipedia, Batcher odd even merge sort

Prog

(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)])

Crossrefs

Cf. A000079, A350567.

Sequence in context: A061562 A006282 A086845 * A243205 A259368 A175098

Adjacent sequences: A375646 A375647 A375648 * A375650 A375651 A375652

Keyword

nonn

Author

Darío Clavijo, Aug 22 2024

Status

approved