Cannot understand your results

[MBkkt]

In general with tournament tree we need log(k) comparison on every step, it's not depend by disjoint inputs or not.

With heap decrease (not cpython strange implementation which just make pop + push):

In case of interleaved inputs we need 2*log(n) comparison, but if disjoint inputs, we need only 2 comparison on each next() except next when end of some input

[sweeneyde]

CPython's implementation of _siftup (i.e. which logically converts (x, heap1, heap2) into a heap) is here.

There are at least two possible implementations of this:

• An "optimistic" siftup takes finds the smallest among the root and its two children. If the root is already smallest, we're already done. Otherwise, swap the root and the small child, then repeat the siftup process at the tree where the small child came from.

• A "pessimistic" siftup has two stages: in the first stage, the new root's value is completely ignored, and instead the smaller of the two children is swapped with the root. This is repeated until the new item is at a leaf. In the second stage, the new item is swapped back toward the root until it finds where it belongs (a "siftdown" operation).

As mentioned in the comment in the CPython code, Exercise 18 in Knuth's TAOPC Volume 3, Chapter 5.2.3. is

18. [21] (R. W. Floyd.) During the selection phase of heapsort, the key K tends to be quite small, so that nearly all of the comparisons in step H6 find K < Kj. Show how to modify the algorithm so that K is not compared with Kj in the main loop of the computation, thereby nearly cutting the average number of comparisons in half.

This is Knuth advocating for the "pessimistic" approach when doing a heapsort, since it requires one comparison per level rather than two (followed by the siftdown, which should typically take fewer steps: half of a tree's nodes belong as leaves, 3/4 are at most one away from a leaf, 7/8 are at most two away, etc.).

The pessimistic approach is especially beneficial for heappops, since heappops swap the last node into the root, and so that root will very often end up as a leaf, and the siftdown does nothing. But pessimism seems to also be beneficial for random heapify() calls.

You're right that the iterators-don't-overlap test case is greatly benefitted by using the optimistic approach. But that is still at the expense of the average case and the worst case. I did some testing here. That gave these results:

======= heap merge, pessimistic siftup ======
No overlap: 65,004 lt; 65,004 eq
Interleaved: 64,004 lt; 64,004 eq
Even Random1: 76,370 lt; 76,370 eq
Even Random2: 76,186 lt; 76,186 eq
Even Random3: 76,110 lt; 76,110 eq
Uneven Random1: 76,309 lt; 76,309 eq
Uneven Random2: 76,161 lt; 76,161 eq
Uneven Random3: 76,410 lt; 76,410 eq

======= heap merge, optimistic siftup ======
No overlap: 29,054 lt; 29,054 eq
Interleaved: 99,234 lt; 99,234 eq
Even Random1: 89,972 lt; 89,972 eq
Even Random2: 90,170 lt; 90,170 eq
Even Random3: 90,093 lt; 90,093 eq
Uneven Random1: 90,049 lt; 90,049 eq
Uneven Random2: 90,112 lt; 90,112 eq
Uneven Random3: 89,820 lt; 89,820 eq

==== multimerge.merge ====
No overlap: 32,000 lt; 0 eq
Interleaved: 63,968 lt; 0 eq
Even Random1: 63,967 lt; 0 eq
Even Random2: 63,966 lt; 0 eq
Even Random3: 63,966 lt; 0 eq
Uneven Random1: 63,974 lt; 0 eq
Uneven Random2: 63,970 lt; 0 eq
Uneven Random3: 63,978 lt; 0 eq

(edited because `assert a == sorted(a)` shouldn't be measured)

[sweeneyde]

Another way the tournament tree benefits from the particular case of (0..999), (1_000..1_999), (2_000..2_999), ... is that once the (0..999) is exhausted, the (1_000..1_999) gets promoted in the tree, and no re-balancing is attempted, so each item from (1_000, 1_999) takes one fewer comparison to produce. If you want to test cases where no iterators are exhausted, my same script will work with the following modification:

 def comparisons(mergefunc, iterables):
     Int.lt = Int.eq = 0
-    a = list(mergefunc(*iterables))
+    it = mergefunc(*iterables)
+    a = [next(it) for _ in range(500)]
     result = Int.lt, Int.eq
     assert a == sorted(range(len(a)))
     return result

This results in

======= heap merge, pessimistic siftup ======
No overlap: 3,519 lt; 3,519 eq
Interleaved: 2,022 lt; 2,022 eq
Even Random1: 2,403 lt; 2,403 eq
Even Random2: 2,368 lt; 2,368 eq
Even Random3: 2,369 lt; 2,369 eq
Uneven Random1: 2,419 lt; 2,419 eq
Uneven Random2: 2,401 lt; 2,401 eq
Uneven Random3: 2,434 lt; 2,434 eq

======= heap merge, optimistic siftup ======
No overlap: 1,024 lt; 1,024 eq
Interleaved: 3,122 lt; 3,122 eq
Even Random1: 2,851 lt; 2,851 eq
Even Random2: 2,863 lt; 2,863 eq
Even Random3: 2,819 lt; 2,819 eq
Uneven Random1: 2,793 lt; 2,793 eq
Uneven Random2: 2,809 lt; 2,809 eq
Uneven Random3: 2,787 lt; 2,787 eq

==== multimerge.merge ====
No overlap: 2,011 lt; 0 eq
Interleaved: 2,011 lt; 0 eq
Even Random1: 2,011 lt; 0 eq
Even Random2: 2,011 lt; 0 eq
Even Random3: 2,011 lt; 0 eq
Uneven Random1: 2,011 lt; 0 eq
Uneven Random2: 2,011 lt; 0 eq
Uneven Random3: 2,011 lt; 0 eq

[sweeneyde]

The information-theoretical optimum to retrieve the first 500 among 16 sorted iterables is log_2(16**500) == 2000 comparisons, so this is about as good as we can do! (considering we also have computed the data to keep iterating later).

The information-theoretical optimum to merge k iterables of length m each is

$$ \log_2\binom{km}{m,m,\dots, m} = \log_2\left(\frac{(km)!}{(m!)^k}\right) = \log_2((km)!) - k \log2(m!) \approx \left(km+\frac{1}{2}\right)\log{2}k-\frac{\left(k-1\right)}{2}\log{2}m-\left(k-1\right)\log{2}\left(\sqrt{2\pi}\right) $$

Plugging in $k=16$ and $m=1000$ gives $63907.37$, so the performance with exhausted iterators is pretty good too.

[MBkkt]

Thanks! Now your results looks understandable for me. Btw eq can be avoided in heap

[MBkkt]

so this is about as good as we can do

For interleaved data yes!

But for not overlapped it's like log(k) * k + n (You can see it in heap sift up)

Interleaved: 3,122 lt;

It's because python implementation is really bad. https://github.com/python/cpython/blob/main/Lib/heapq.py#L260

Good implementation: https://github.com/llvm/llvm-project/blob/main/libcxx/include/__algorithm/sift_down.h#L26

sift down because max heap (it's opposite to cpython naming)

So in general I think good heap implementation on random data outperform tournament tree

Anyway I plan to write benchmarks and check it

https://github.com/iresearch-toolkit/iresearch/pull/476

[MBkkt]

For tree it is always log(k) per element, for heap it's a lot of more optimistic, and if our data in average at least three times win in row, it will be better

[MBkkt]

Another important note worst case for heap, worse in two times, but best case better in ~log(k) times

[sweeneyde]

What you describe as "good" and "really bad" implementations are what I was describing as "optimistic" and "pessimistic".

It might be surprising, but the pessimistic version (like CPython's) does fewer data comparisons on average for random data, for the reasons I already described, and as the comment above the code describes, and what Knuth's TAOCP exercise describes. Of course, if you suspect there will be many streaks in your data, your mileage may vary.

The actual performance is different than the number of comparisons though: the more relatively expensive your comparison function, the more just the number matters. Since object comparison can be arbitrarily expensive in Python, I do not plan to change anything here.

P.S. The other thing to consider is sort stability. Stability is implied by the contract of heapq.merge, and that's why the __eq__ comparisons are happening: each item is stored in a tuple alongside the index of the iterator from which it came. Comparing the tuples (x1, i1, ...) < (x2, i2, ...) is implemented like (i1 < i2) if (x1 != x2) else (x1 < x2) in Python. One could re-implement it as (not x2 < x1) if (i1 < i2) else (x1 < x2), but since that's not what's implemented for tuples, it's not worth the bother. If you don't need stability, another thing to try would be the "tournament tree of losers", where instead of storing the winner of each comparison, you store the loser, and that way each next(...) call moves from the leaf strictly up the tree.

[MBkkt]

Yes you're right, I was completely wrong, btw I adopted your code to test it a little:

import heapq
import multimerge

# Copied from libc++, max heap, so gt
# first_child, we can remember max child, it's optimization
def sift_down(heap, start, first_child = 0):
    size = len(heap)
    child = start
    if size < 2 or (size - 2) // 2 < child:
        return first_child

    if first_child == 0:
        first_child = 2 * child + 1
        if first_child + 1 < size and heap[first_child][0] > heap[first_child + 1][0]:
            first_child += 1
    child = first_child

    top = heap[start]
    if heap[child][0] > top[0]:
        return first_child
    while True:
        heap[start] = heap[child]
        start = child
        if (size - 2) // 2 < child:
            break
        child = 2 * child + 1
        if child + 1 < size and heap[child][0] > heap[child + 1][0]:
            child += 1
        if heap[child][0] > top[0]:
            break
    heap[start] = top
    return 0

def make_heap(heap):
    size = len(heap)
    if size < 2:
        return
    for i in range((size - 2) // 2, -1, -1):
        sift_down(heap, i)

enable_count = True

def heap_merge(*iterables):
    global enable_count
    h = []
    h_append = h.append
    for it in map(iter, iterables):
        try:
            next = it.__next__
            h_append([next(), next])
        except StopIteration:
            pass
    make_heap(h)
    first_child = 0
    while len(h) != 0:
        try:
            while True:
                yield h[0][0]
                h[0][0] = h[0][1]()
                first_child = sift_down(h, 0, first_child)
        except StopIteration:
            h[0] = h[-1]
            h.pop()
            # enable_count = False
            # It can be implemented better I just lazy but it's not really affect
            first_child = sift_down(h, 0)
            # enable_count = True

class Int(int):
    lt = gt = eq = 0
    def __lt__(self, other):
        if enable_count:
            __class__.lt += 1
        return int.__lt__(self, other)

    def __gt__(self, other):
        if enable_count:
            __class__.gt += 1
        return int.__gt__(self, other)

    def __eq__(self, other):
        if enable_count:
            __class__.eq += 1
        return int.__eq__(self, other)

def comparisons(mergefunc, iterables):
    Int.lt = Int.gt = Int.eq = 0
    a = list(mergefunc(*iterables))
    result = Int.lt, Int.gt, Int.eq
    if a != sorted(a):
        print(a)
        assert False
    return result

K = 0
N = 0

from random import Random

def randomized(seed):
    data = [x for x in range(0, K * N)]
    r = Random(seed)
    r.shuffle(data)
    sep = sorted([r.randrange(K * N) for x in range(0, K - 1)])
    first = 0
    result = []
    size = 0
    for i in sep:
        result.append(list(map(Int, sorted(data[first:i]))))
        size += len(result[-1])
        first = i
    result.append(list(map(Int, sorted(data[first:]))))
    size += len(result[-1])
    assert size == N * K
    return result

def test_merge_func(mergefunc):
    no_overlap = [
        # (0..999), (1_000..1_999), (2_000..2_999), ...
        list(map(Int, range(x, x+N)))
        for x in range(0, K * N, N)
    ]
    interleaved = [
        # (0,16,32,...), (1,17,33,...), (2,18,34,...), ...
        list(map(Int, range(x, K * N, K)))
        for x in range(K)
    ]
    randomized42 = randomized(42)
    randomized93 = randomized(93)
    randomized11111 = randomized(11111)
    # print(len(no_overlap))
    # print(len(interleaved))
    # print(len(randomized42))
    # print(len(randomized93))
    # print(len(randomized11111))
    print("No overlap: {:,} lt; {:,} gt; {:,} eq".format(
        *comparisons(mergefunc, no_overlap)))
    print("Interleaved: {:,} lt; {:,} gt; {:,} eq".format(
        *comparisons(mergefunc, interleaved)))
    print("randomized42: {:,} lt; {:,} gt; {:,} eq".format(
        *comparisons(mergefunc, randomized42)))
    print("randomized93: {:,} lt; {:,} gt; {:,} eq".format(
        *comparisons(mergefunc, randomized93)))
    print("randomized11111: {:,} lt; {:,} gt; {:,} eq".format(
        *comparisons(mergefunc, randomized11111)))

if __name__ == "__main__":
    for k in range(1, 10):
        for n in range(0, 10):
            K, N = 2**k, 2**n
            print(f"K={K} N={N}")
            print("======= siftdown ======")
            test_merge_func(lambda *its: heap_merge(*its))
            print()

            print("======= heapq.merge ======")
            test_merge_func(lambda *its: heapq.merge(*its))
            print()

            print("==== multimerge.merge ====")
            test_merge_func(multimerge.merge)
            print()

Results:

[Running] python -u "/home/mbkkt/Work/kwaymerge.py"
K=2 N=1
======= siftdown ======
No overlap: 0 lt; 1 gt; 0 eq
Interleaved: 0 lt; 1 gt; 0 eq
randomized42: 0 lt; 0 gt; 0 eq
randomized93: 0 lt; 1 gt; 0 eq
randomized11111: 0 lt; 0 gt; 0 eq

======= heapq.merge ======
No overlap: 1 lt; 0 gt; 1 eq
Interleaved: 1 lt; 0 gt; 1 eq
randomized42: 0 lt; 0 gt; 0 eq
randomized93: 1 lt; 0 gt; 1 eq
randomized11111: 0 lt; 0 gt; 0 eq

==== multimerge.merge ====
No overlap: 1 lt; 0 gt; 0 eq
Interleaved: 1 lt; 0 gt; 0 eq
randomized42: 0 lt; 0 gt; 0 eq
randomized93: 1 lt; 0 gt; 0 eq
randomized11111: 0 lt; 0 gt; 0 eq

K=2 N=2
======= siftdown ======
No overlap: 0 lt; 2 gt; 0 eq
Interleaved: 0 lt; 3 gt; 0 eq
randomized42: 0 lt; 3 gt; 0 eq
randomized93: 0 lt; 0 gt; 0 eq
randomized11111: 0 lt; 3 gt; 0 eq

======= heapq.merge ======
No overlap: 2 lt; 0 gt; 2 eq
Interleaved: 3 lt; 0 gt; 3 eq
randomized42: 3 lt; 0 gt; 3 eq
randomized93: 0 lt; 0 gt; 0 eq
randomized11111: 3 lt; 0 gt; 3 eq

==== multimerge.merge ====
No overlap: 2 lt; 0 gt; 0 eq
Interleaved: 3 lt; 0 gt; 0 eq
randomized42: 3 lt; 0 gt; 0 eq
randomized93: 0 lt; 0 gt; 0 eq
randomized11111: 3 lt; 0 gt; 0 eq

K=2 N=4
======= siftdown ======
No overlap: 0 lt; 4 gt; 0 eq
Interleaved: 0 lt; 7 gt; 0 eq
randomized42: 0 lt; 4 gt; 0 eq
randomized93: 0 lt; 7 gt; 0 eq
randomized11111: 0 lt; 5 gt; 0 eq

======= heapq.merge ======
No overlap: 4 lt; 0 gt; 4 eq
Interleaved: 7 lt; 0 gt; 7 eq
randomized42: 4 lt; 0 gt; 4 eq
randomized93: 7 lt; 0 gt; 7 eq
randomized11111: 5 lt; 0 gt; 5 eq

==== multimerge.merge ====
No overlap: 4 lt; 0 gt; 0 eq
Interleaved: 7 lt; 0 gt; 0 eq
randomized42: 4 lt; 0 gt; 0 eq
randomized93: 7 lt; 0 gt; 0 eq
randomized11111: 5 lt; 0 gt; 0 eq

K=2 N=8
======= siftdown ======
No overlap: 0 lt; 8 gt; 0 eq
Interleaved: 0 lt; 15 gt; 0 eq
randomized42: 0 lt; 15 gt; 0 eq
randomized93: 0 lt; 9 gt; 0 eq
randomized11111: 0 lt; 15 gt; 0 eq

======= heapq.merge ======
No overlap: 8 lt; 0 gt; 8 eq
Interleaved: 15 lt; 0 gt; 15 eq
randomized42: 15 lt; 0 gt; 15 eq
randomized93: 9 lt; 0 gt; 9 eq
randomized11111: 15 lt; 0 gt; 15 eq

==== multimerge.merge ====
No overlap: 8 lt; 0 gt; 0 eq
Interleaved: 15 lt; 0 gt; 0 eq
randomized42: 15 lt; 0 gt; 0 eq
randomized93: 9 lt; 0 gt; 0 eq
randomized11111: 15 lt; 0 gt; 0 eq

K=2 N=16
======= siftdown ======
No overlap: 0 lt; 16 gt; 0 eq
Interleaved: 0 lt; 31 gt; 0 eq
randomized42: 0 lt; 31 gt; 0 eq
randomized93: 0 lt; 31 gt; 0 eq
randomized11111: 0 lt; 31 gt; 0 eq

======= heapq.merge ======
No overlap: 16 lt; 0 gt; 16 eq
Interleaved: 31 lt; 0 gt; 31 eq
randomized42: 31 lt; 0 gt; 31 eq
randomized93: 31 lt; 0 gt; 31 eq
randomized11111: 31 lt; 0 gt; 31 eq

==== multimerge.merge ====
No overlap: 16 lt; 0 gt; 0 eq
Interleaved: 31 lt; 0 gt; 0 eq
randomized42: 31 lt; 0 gt; 0 eq
randomized93: 31 lt; 0 gt; 0 eq
randomized11111: 31 lt; 0 gt; 0 eq

K=2 N=32
======= siftdown ======
No overlap: 0 lt; 32 gt; 0 eq
Interleaved: 0 lt; 63 gt; 0 eq
randomized42: 0 lt; 60 gt; 0 eq
randomized93: 0 lt; 63 gt; 0 eq
randomized11111: 0 lt; 55 gt; 0 eq

======= heapq.merge ======
No overlap: 32 lt; 0 gt; 32 eq
Interleaved: 63 lt; 0 gt; 63 eq
randomized42: 60 lt; 0 gt; 60 eq
randomized93: 63 lt; 0 gt; 63 eq
randomized11111: 55 lt; 0 gt; 55 eq

==== multimerge.merge ====
No overlap: 32 lt; 0 gt; 0 eq
Interleaved: 63 lt; 0 gt; 0 eq
randomized42: 60 lt; 0 gt; 0 eq
randomized93: 63 lt; 0 gt; 0 eq
randomized11111: 55 lt; 0 gt; 0 eq

K=2 N=64
======= siftdown ======
No overlap: 0 lt; 64 gt; 0 eq
Interleaved: 0 lt; 127 gt; 0 eq
randomized42: 0 lt; 124 gt; 0 eq
randomized93: 0 lt; 89 gt; 0 eq
randomized11111: 0 lt; 87 gt; 0 eq

======= heapq.merge ======
No overlap: 64 lt; 0 gt; 64 eq
Interleaved: 127 lt; 0 gt; 127 eq
randomized42: 124 lt; 0 gt; 124 eq
randomized93: 89 lt; 0 gt; 89 eq
randomized11111: 87 lt; 0 gt; 87 eq

==== multimerge.merge ====
No overlap: 64 lt; 0 gt; 0 eq
Interleaved: 127 lt; 0 gt; 0 eq
randomized42: 124 lt; 0 gt; 0 eq
randomized93: 89 lt; 0 gt; 0 eq
randomized11111: 87 lt; 0 gt; 0 eq

K=2 N=128
======= siftdown ======
No overlap: 0 lt; 128 gt; 0 eq
Interleaved: 0 lt; 255 gt; 0 eq
randomized42: 0 lt; 253 gt; 0 eq
randomized93: 0 lt; 250 gt; 0 eq
randomized11111: 0 lt; 255 gt; 0 eq

======= heapq.merge ======
No overlap: 128 lt; 0 gt; 128 eq
Interleaved: 255 lt; 0 gt; 255 eq
randomized42: 253 lt; 0 gt; 253 eq
randomized93: 250 lt; 0 gt; 250 eq
randomized11111: 255 lt; 0 gt; 255 eq

==== multimerge.merge ====
No overlap: 128 lt; 0 gt; 0 eq
Interleaved: 255 lt; 0 gt; 0 eq
randomized42: 253 lt; 0 gt; 0 eq
randomized93: 250 lt; 0 gt; 0 eq
randomized11111: 255 lt; 0 gt; 0 eq

K=2 N=256
======= siftdown ======
No overlap: 0 lt; 256 gt; 0 eq
Interleaved: 0 lt; 511 gt; 0 eq
randomized42: 0 lt; 499 gt; 0 eq
randomized93: 0 lt; 507 gt; 0 eq
randomized11111: 0 lt; 511 gt; 0 eq

======= heapq.merge ======
No overlap: 256 lt; 0 gt; 256 eq
Interleaved: 511 lt; 0 gt; 511 eq
randomized42: 499 lt; 0 gt; 499 eq
randomized93: 507 lt; 0 gt; 507 eq
randomized11111: 511 lt; 0 gt; 511 eq

==== multimerge.merge ====
No overlap: 256 lt; 0 gt; 0 eq
Interleaved: 511 lt; 0 gt; 0 eq
randomized42: 499 lt; 0 gt; 0 eq
randomized93: 507 lt; 0 gt; 0 eq
randomized11111: 511 lt; 0 gt; 0 eq

K=2 N=512
======= siftdown ======
No overlap: 0 lt; 512 gt; 0 eq
Interleaved: 0 lt; 1,023 gt; 0 eq
randomized42: 0 lt; 1,010 gt; 0 eq
randomized93: 0 lt; 1,013 gt; 0 eq
randomized11111: 0 lt; 1,021 gt; 0 eq

======= heapq.merge ======
No overlap: 512 lt; 0 gt; 512 eq
Interleaved: 1,023 lt; 0 gt; 1,023 eq
randomized42: 1,010 lt; 0 gt; 1,010 eq
randomized93: 1,013 lt; 0 gt; 1,013 eq
randomized11111: 1,021 lt; 0 gt; 1,021 eq

==== multimerge.merge ====
No overlap: 512 lt; 0 gt; 0 eq
Interleaved: 1,023 lt; 0 gt; 0 eq
randomized42: 1,010 lt; 0 gt; 0 eq
randomized93: 1,013 lt; 0 gt; 0 eq
randomized11111: 1,021 lt; 0 gt; 0 eq

K=4 N=1
======= siftdown ======
No overlap: 0 lt; 6 gt; 0 eq
Interleaved: 0 lt; 6 gt; 0 eq
randomized42: 0 lt; 3 gt; 0 eq
randomized93: 0 lt; 2 gt; 0 eq
randomized11111: 0 lt; 4 gt; 0 eq

======= heapq.merge ======
No overlap: 7 lt; 0 gt; 7 eq
Interleaved: 7 lt; 0 gt; 7 eq
randomized42: 3 lt; 0 gt; 3 eq
randomized93: 2 lt; 0 gt; 2 eq
randomized11111: 4 lt; 0 gt; 4 eq

==== multimerge.merge ====
No overlap: 4 lt; 0 gt; 0 eq
Interleaved: 4 lt; 0 gt; 0 eq
randomized42: 3 lt; 0 gt; 0 eq
randomized93: 2 lt; 0 gt; 0 eq
randomized11111: 4 lt; 0 gt; 0 eq

K=4 N=2
======= siftdown ======
No overlap: 0 lt; 11 gt; 0 eq
Interleaved: 0 lt; 17 gt; 0 eq
randomized42: 0 lt; 6 gt; 0 eq
randomized93: 0 lt; 12 gt; 0 eq
randomized11111: 0 lt; 11 gt; 0 eq

======= heapq.merge ======
No overlap: 13 lt; 0 gt; 13 eq
Interleaved: 15 lt; 0 gt; 15 eq
randomized42: 6 lt; 0 gt; 6 eq
randomized93: 13 lt; 0 gt; 13 eq
randomized11111: 11 lt; 0 gt; 11 eq

==== multimerge.merge ====
No overlap: 8 lt; 0 gt; 0 eq
Interleaved: 12 lt; 0 gt; 0 eq
randomized42: 6 lt; 0 gt; 0 eq
randomized93: 12 lt; 0 gt; 0 eq
randomized11111: 9 lt; 0 gt; 0 eq

K=4 N=4
======= siftdown ======
No overlap: 0 lt; 17 gt; 0 eq
Interleaved: 0 lt; 38 gt; 0 eq
randomized42: 0 lt; 21 gt; 0 eq
randomized93: 0 lt; 23 gt; 0 eq
randomized11111: 0 lt; 28 gt; 0 eq

======= heapq.merge ======
No overlap: 25 lt; 0 gt; 25 eq
Interleaved: 31 lt; 0 gt; 31 eq
randomized42: 28 lt; 0 gt; 28 eq
randomized93: 29 lt; 0 gt; 29 eq
randomized11111: 34 lt; 0 gt; 34 eq

==== multimerge.merge ====
No overlap: 16 lt; 0 gt; 0 eq
Interleaved: 28 lt; 0 gt; 0 eq
randomized42: 23 lt; 0 gt; 0 eq
randomized93: 23 lt; 0 gt; 0 eq
randomized11111: 28 lt; 0 gt; 0 eq

K=4 N=8
======= siftdown ======
No overlap: 0 lt; 29 gt; 0 eq
Interleaved: 0 lt; 81 gt; 0 eq
randomized42: 0 lt; 56 gt; 0 eq
randomized93: 0 lt; 38 gt; 0 eq
randomized11111: 0 lt; 53 gt; 0 eq

======= heapq.merge ======
No overlap: 49 lt; 0 gt; 49 eq
Interleaved: 63 lt; 0 gt; 63 eq
randomized42: 69 lt; 0 gt; 69 eq
randomized93: 51 lt; 0 gt; 51 eq
randomized11111: 67 lt; 0 gt; 67 eq

==== multimerge.merge ====
No overlap: 32 lt; 0 gt; 0 eq
Interleaved: 60 lt; 0 gt; 0 eq
randomized42: 54 lt; 0 gt; 0 eq
randomized93: 47 lt; 0 gt; 0 eq
randomized11111: 54 lt; 0 gt; 0 eq

K=4 N=16
======= siftdown ======
No overlap: 0 lt; 53 gt; 0 eq
Interleaved: 0 lt; 166 gt; 0 eq
randomized42: 0 lt; 137 gt; 0 eq
randomized93: 0 lt; 136 gt; 0 eq
randomized11111: 0 lt; 124 gt; 0 eq

======= heapq.merge ======
No overlap: 97 lt; 0 gt; 97 eq
Interleaved: 127 lt; 0 gt; 127 eq
randomized42: 150 lt; 0 gt; 150 eq
randomized93: 150 lt; 0 gt; 150 eq
randomized11111: 147 lt; 0 gt; 147 eq

==== multimerge.merge ====
No overlap: 64 lt; 0 gt; 0 eq
Interleaved: 124 lt; 0 gt; 0 eq
randomized42: 122 lt; 0 gt; 0 eq
randomized93: 125 lt; 0 gt; 0 eq
randomized11111: 119 lt; 0 gt; 0 eq

K=4 N=32
======= siftdown ======
No overlap: 0 lt; 101 gt; 0 eq
Interleaved: 0 lt; 337 gt; 0 eq
randomized42: 0 lt; 191 gt; 0 eq
randomized93: 0 lt; 284 gt; 0 eq
randomized11111: 0 lt; 237 gt; 0 eq

======= heapq.merge ======
No overlap: 193 lt; 0 gt; 193 eq
Interleaved: 255 lt; 0 gt; 255 eq
randomized42: 241 lt; 0 gt; 241 eq
randomized93: 301 lt; 0 gt; 301 eq
randomized11111: 289 lt; 0 gt; 289 eq

==== multimerge.merge ====
No overlap: 128 lt; 0 gt; 0 eq
Interleaved: 252 lt; 0 gt; 0 eq
randomized42: 175 lt; 0 gt; 0 eq
randomized93: 237 lt; 0 gt; 0 eq
randomized11111: 246 lt; 0 gt; 0 eq

K=4 N=64
======= siftdown ======
No overlap: 0 lt; 197 gt; 0 eq
Interleaved: 0 lt; 678 gt; 0 eq
randomized42: 0 lt; 417 gt; 0 eq
randomized93: 0 lt; 428 gt; 0 eq
randomized11111: 0 lt; 498 gt; 0 eq

======= heapq.merge ======
No overlap: 385 lt; 0 gt; 385 eq
Interleaved: 511 lt; 0 gt; 511 eq
randomized42: 613 lt; 0 gt; 613 eq
randomized93: 641 lt; 0 gt; 641 eq
randomized11111: 607 lt; 0 gt; 607 eq

==== multimerge.merge ====
No overlap: 256 lt; 0 gt; 0 eq
Interleaved: 508 lt; 0 gt; 0 eq
randomized42: 498 lt; 0 gt; 0 eq
randomized93: 488 lt; 0 gt; 0 eq
randomized11111: 507 lt; 0 gt; 0 eq

K=4 N=128
======= siftdown ======
No overlap: 0 lt; 389 gt; 0 eq
Interleaved: 0 lt; 1,361 gt; 0 eq
randomized42: 0 lt; 958 gt; 0 eq
randomized93: 0 lt; 891 gt; 0 eq
randomized11111: 0 lt; 877 gt; 0 eq

======= heapq.merge ======
No overlap: 769 lt; 0 gt; 769 eq
Interleaved: 1,023 lt; 0 gt; 1,023 eq
randomized42: 1,274 lt; 0 gt; 1,274 eq
randomized93: 1,273 lt; 0 gt; 1,273 eq
randomized11111: 1,194 lt; 0 gt; 1,194 eq

==== multimerge.merge ====
No overlap: 512 lt; 0 gt; 0 eq
Interleaved: 1,020 lt; 0 gt; 0 eq
randomized42: 1,013 lt; 0 gt; 0 eq
randomized93: 982 lt; 0 gt; 0 eq
randomized11111: 861 lt; 0 gt; 0 eq

K=4 N=256
======= siftdown ======
No overlap: 0 lt; 773 gt; 0 eq
Interleaved: 0 lt; 2,726 gt; 0 eq
randomized42: 0 lt; 1,830 gt; 0 eq
randomized93: 0 lt; 2,035 gt; 0 eq
randomized11111: 0 lt; 2,222 gt; 0 eq

======= heapq.merge ======
No overlap: 1,537 lt; 0 gt; 1,537 eq
Interleaved: 2,047 lt; 0 gt; 2,047 eq
randomized42: 2,526 lt; 0 gt; 2,526 eq
randomized93: 2,504 lt; 0 gt; 2,504 eq
randomized11111: 2,543 lt; 0 gt; 2,543 eq

==== multimerge.merge ====
No overlap: 1,024 lt; 0 gt; 0 eq
Interleaved: 2,044 lt; 0 gt; 0 eq
randomized42: 2,028 lt; 0 gt; 0 eq
randomized93: 2,040 lt; 0 gt; 0 eq
randomized11111: 2,045 lt; 0 gt; 0 eq

K=4 N=512
======= siftdown ======
No overlap: 0 lt; 1,541 gt; 0 eq
Interleaved: 0 lt; 5,457 gt; 0 eq
randomized42: 0 lt; 3,741 gt; 0 eq
randomized93: 0 lt; 4,352 gt; 0 eq
randomized11111: 0 lt; 4,207 gt; 0 eq

======= heapq.merge ======
No overlap: 3,073 lt; 0 gt; 3,073 eq
Interleaved: 4,095 lt; 0 gt; 4,095 eq
randomized42: 5,138 lt; 0 gt; 5,138 eq
randomized93: 5,031 lt; 0 gt; 5,031 eq
randomized11111: 5,120 lt; 0 gt; 5,120 eq

==== multimerge.merge ====
No overlap: 2,048 lt; 0 gt; 0 eq
Interleaved: 4,092 lt; 0 gt; 0 eq
randomized42: 4,077 lt; 0 gt; 0 eq
randomized93: 4,083 lt; 0 gt; 0 eq
randomized11111: 4,076 lt; 0 gt; 0 eq

K=8 N=1
======= siftdown ======
No overlap: 0 lt; 24 gt; 0 eq
Interleaved: 0 lt; 24 gt; 0 eq
randomized42: 0 lt; 13 gt; 0 eq
randomized93: 0 lt; 14 gt; 0 eq
randomized11111: 0 lt; 23 gt; 0 eq

======= heapq.merge ======
No overlap: 25 lt; 0 gt; 25 eq
Interleaved: 25 lt; 0 gt; 25 eq
randomized42: 13 lt; 0 gt; 13 eq
randomized93: 15 lt; 0 gt; 15 eq
randomized11111: 22 lt; 0 gt; 22 eq

==== multimerge.merge ====
No overlap: 12 lt; 0 gt; 0 eq
Interleaved: 12 lt; 0 gt; 0 eq
randomized42: 10 lt; 0 gt; 0 eq
randomized93: 13 lt; 0 gt; 0 eq
randomized11111: 14 lt; 0 gt; 0 eq

K=8 N=2
======= siftdown ======
No overlap: 0 lt; 37 gt; 0 eq
Interleaved: 0 lt; 59 gt; 0 eq
randomized42: 0 lt; 38 gt; 0 eq
randomized93: 0 lt; 43 gt; 0 eq
randomized11111: 0 lt; 30 gt; 0 eq

======= heapq.merge ======
No overlap: 47 lt; 0 gt; 47 eq
Interleaved: 50 lt; 0 gt; 50 eq
randomized42: 48 lt; 0 gt; 48 eq
randomized93: 42 lt; 0 gt; 42 eq
randomized11111: 36 lt; 0 gt; 36 eq

==== multimerge.merge ====
No overlap: 24 lt; 0 gt; 0 eq
Interleaved: 36 lt; 0 gt; 0 eq
randomized42: 34 lt; 0 gt; 0 eq
randomized93: 30 lt; 0 gt; 0 eq
randomized11111: 37 lt; 0 gt; 0 eq

K=8 N=4
======= siftdown ======
No overlap: 0 lt; 51 gt; 0 eq
Interleaved: 0 lt; 127 gt; 0 eq
randomized42: 0 lt; 104 gt; 0 eq
randomized93: 0 lt; 67 gt; 0 eq
randomized11111: 0 lt; 91 gt; 0 eq

======= heapq.merge ======
No overlap: 91 lt; 0 gt; 91 eq
Interleaved: 95 lt; 0 gt; 95 eq
randomized42: 99 lt; 0 gt; 99 eq
randomized93: 100 lt; 0 gt; 100 eq
randomized11111: 96 lt; 0 gt; 96 eq

==== multimerge.merge ====
No overlap: 48 lt; 0 gt; 0 eq
Interleaved: 84 lt; 0 gt; 0 eq
randomized42: 80 lt; 0 gt; 0 eq
randomized93: 79 lt; 0 gt; 0 eq
randomized11111: 75 lt; 0 gt; 0 eq

K=8 N=8
======= siftdown ======
No overlap: 0 lt; 79 gt; 0 eq
Interleaved: 0 lt; 269 gt; 0 eq
randomized42: 0 lt; 236 gt; 0 eq
randomized93: 0 lt; 201 gt; 0 eq
randomized11111: 0 lt; 214 gt; 0 eq

======= heapq.merge ======
No overlap: 179 lt; 0 gt; 179 eq
Interleaved: 192 lt; 0 gt; 192 eq
randomized42: 236 lt; 0 gt; 236 eq
randomized93: 205 lt; 0 gt; 205 eq
randomized11111: 204 lt; 0 gt; 204 eq

==== multimerge.merge ====
No overlap: 96 lt; 0 gt; 0 eq
Interleaved: 180 lt; 0 gt; 0 eq
randomized42: 180 lt; 0 gt; 0 eq
randomized93: 167 lt; 0 gt; 0 eq
randomized11111: 157 lt; 0 gt; 0 eq

K=8 N=16
======= siftdown ======
No overlap: 0 lt; 135 gt; 0 eq
Interleaved: 0 lt; 550 gt; 0 eq
randomized42: 0 lt; 311 gt; 0 eq
randomized93: 0 lt; 424 gt; 0 eq
randomized11111: 0 lt; 413 gt; 0 eq

======= heapq.merge ======
No overlap: 355 lt; 0 gt; 355 eq
Interleaved: 386 lt; 0 gt; 386 eq
randomized42: 388 lt; 0 gt; 388 eq
randomized93: 469 lt; 0 gt; 469 eq
randomized11111: 424 lt; 0 gt; 424 eq

==== multimerge.merge ====
No overlap: 192 lt; 0 gt; 0 eq
Interleaved: 372 lt; 0 gt; 0 eq
randomized42: 263 lt; 0 gt; 0 eq
randomized93: 366 lt; 0 gt; 0 eq
randomized11111: 352 lt; 0 gt; 0 eq

K=8 N=32
======= siftdown ======
No overlap: 0 lt; 247 gt; 0 eq
Interleaved: 0 lt; 1,109 gt; 0 eq
randomized42: 0 lt; 819 gt; 0 eq
randomized93: 0 lt; 863 gt; 0 eq
randomized11111: 0 lt; 913 gt; 0 eq

======= heapq.merge ======
No overlap: 707 lt; 0 gt; 707 eq
Interleaved: 767 lt; 0 gt; 767 eq
randomized42: 967 lt; 0 gt; 967 eq
randomized93: 971 lt; 0 gt; 971 eq
randomized11111: 948 lt; 0 gt; 948 eq

==== multimerge.merge ====
No overlap: 384 lt; 0 gt; 0 eq
Interleaved: 756 lt; 0 gt; 0 eq
randomized42: 743 lt; 0 gt; 0 eq
randomized93: 741 lt; 0 gt; 0 eq
randomized11111: 750 lt; 0 gt; 0 eq

K=8 N=64
======= siftdown ======
No overlap: 0 lt; 471 gt; 0 eq
Interleaved: 0 lt; 2,232 gt; 0 eq
randomized42: 0 lt; 1,743 gt; 0 eq
randomized93: 0 lt; 1,564 gt; 0 eq
randomized11111: 0 lt; 1,716 gt; 0 eq

======= heapq.merge ======
No overlap: 1,411 lt; 0 gt; 1,411 eq
Interleaved: 1,537 lt; 0 gt; 1,537 eq
randomized42: 1,969 lt; 0 gt; 1,969 eq
randomized93: 1,991 lt; 0 gt; 1,991 eq
randomized11111: 1,892 lt; 0 gt; 1,892 eq

==== multimerge.merge ====
No overlap: 768 lt; 0 gt; 0 eq
Interleaved: 1,524 lt; 0 gt; 0 eq
randomized42: 1,490 lt; 0 gt; 0 eq
randomized93: 1,463 lt; 0 gt; 0 eq
randomized11111: 1,451 lt; 0 gt; 0 eq

K=8 N=128
======= siftdown ======
No overlap: 0 lt; 919 gt; 0 eq
Interleaved: 0 lt; 4,475 gt; 0 eq
randomized42: 0 lt; 3,771 gt; 0 eq
randomized93: 0 lt; 3,941 gt; 0 eq
randomized11111: 0 lt; 3,631 gt; 0 eq

======= heapq.merge ======
No overlap: 2,819 lt; 0 gt; 2,819 eq
Interleaved: 3,074 lt; 0 gt; 3,074 eq
randomized42: 3,942 lt; 0 gt; 3,942 eq
randomized93: 3,791 lt; 0 gt; 3,791 eq
randomized11111: 4,005 lt; 0 gt; 4,005 eq

==== multimerge.merge ====
No overlap: 1,536 lt; 0 gt; 0 eq
Interleaved: 3,060 lt; 0 gt; 0 eq
randomized42: 3,057 lt; 0 gt; 0 eq
randomized93: 3,058 lt; 0 gt; 0 eq
randomized11111: 3,047 lt; 0 gt; 0 eq

K=8 N=256
======= siftdown ======
No overlap: 0 lt; 1,815 gt; 0 eq
Interleaved: 0 lt; 8,959 gt; 0 eq
randomized42: 0 lt; 5,747 gt; 0 eq
randomized93: 0 lt; 6,639 gt; 0 eq
randomized11111: 0 lt; 7,612 gt; 0 eq

======= heapq.merge ======
No overlap: 5,635 lt; 0 gt; 5,635 eq
Interleaved: 6,143 lt; 0 gt; 6,143 eq
randomized42: 8,259 lt; 0 gt; 8,259 eq
randomized93: 8,090 lt; 0 gt; 8,090 eq
randomized11111: 7,716 lt; 0 gt; 7,716 eq

==== multimerge.merge ====
No overlap: 3,072 lt; 0 gt; 0 eq
Interleaved: 6,132 lt; 0 gt; 0 eq
randomized42: 6,110 lt; 0 gt; 0 eq
randomized93: 6,100 lt; 0 gt; 0 eq
randomized11111: 6,124 lt; 0 gt; 0 eq

K=8 N=512
======= siftdown ======
No overlap: 0 lt; 3,607 gt; 0 eq
Interleaved: 0 lt; 17,933 gt; 0 eq
randomized42: 0 lt; 13,989 gt; 0 eq
randomized93: 0 lt; 14,760 gt; 0 eq
randomized11111: 0 lt; 13,628 gt; 0 eq

======= heapq.merge ======
No overlap: 11,267 lt; 0 gt; 11,267 eq
Interleaved: 12,288 lt; 0 gt; 12,288 eq
randomized42: 16,050 lt; 0 gt; 16,050 eq
randomized93: 15,669 lt; 0 gt; 15,669 eq
randomized11111: 16,335 lt; 0 gt; 16,335 eq

==== multimerge.merge ====
No overlap: 6,144 lt; 0 gt; 0 eq
Interleaved: 12,276 lt; 0 gt; 0 eq
randomized42: 12,194 lt; 0 gt; 0 eq
randomized93: 12,274 lt; 0 gt; 0 eq
randomized11111: 12,270 lt; 0 gt; 0 eq

K=16 N=1
======= siftdown ======
No overlap: 0 lt; 72 gt; 0 eq
Interleaved: 0 lt; 72 gt; 0 eq
randomized42: 0 lt; 49 gt; 0 eq
randomized93: 0 lt; 67 gt; 0 eq
randomized11111: 0 lt; 55 gt; 0 eq

======= heapq.merge ======
No overlap: 69 lt; 0 gt; 69 eq
Interleaved: 69 lt; 0 gt; 69 eq
randomized42: 51 lt; 0 gt; 51 eq
randomized93: 52 lt; 0 gt; 52 eq
randomized11111: 52 lt; 0 gt; 52 eq

==== multimerge.merge ====
No overlap: 32 lt; 0 gt; 0 eq
Interleaved: 32 lt; 0 gt; 0 eq
randomized42: 36 lt; 0 gt; 0 eq
randomized93: 37 lt; 0 gt; 0 eq
randomized11111: 41 lt; 0 gt; 0 eq

K=16 N=2
======= siftdown ======
No overlap: 0 lt; 101 gt; 0 eq
Interleaved: 0 lt; 172 gt; 0 eq
randomized42: 0 lt; 154 gt; 0 eq
randomized93: 0 lt; 138 gt; 0 eq
randomized11111: 0 lt; 145 gt; 0 eq

======= heapq.merge ======
No overlap: 134 lt; 0 gt; 134 eq
Interleaved: 132 lt; 0 gt; 132 eq
randomized42: 131 lt; 0 gt; 131 eq
randomized93: 126 lt; 0 gt; 126 eq
randomized11111: 128 lt; 0 gt; 128 eq

==== multimerge.merge ====
No overlap: 64 lt; 0 gt; 0 eq
Interleaved: 96 lt; 0 gt; 0 eq
randomized42: 106 lt; 0 gt; 0 eq
randomized93: 98 lt; 0 gt; 0 eq
randomized11111: 97 lt; 0 gt; 0 eq

K=16 N=4
======= siftdown ======
No overlap: 0 lt; 131 gt; 0 eq
Interleaved: 0 lt; 372 gt; 0 eq
randomized42: 0 lt; 290 gt; 0 eq
randomized93: 0 lt; 277 gt; 0 eq
randomized11111: 0 lt; 310 gt; 0 eq

======= heapq.merge ======
No overlap: 264 lt; 0 gt; 264 eq
Interleaved: 263 lt; 0 gt; 263 eq
randomized42: 280 lt; 0 gt; 280 eq
randomized93: 261 lt; 0 gt; 261 eq
randomized11111: 282 lt; 0 gt; 282 eq

==== multimerge.merge ====
No overlap: 128 lt; 0 gt; 0 eq
Interleaved: 224 lt; 0 gt; 0 eq
randomized42: 212 lt; 0 gt; 0 eq
randomized93: 217 lt; 0 gt; 0 eq
randomized11111: 225 lt; 0 gt; 0 eq

K=16 N=8
======= siftdown ======
No overlap: 0 lt; 191 gt; 0 eq
Interleaved: 0 lt; 767 gt; 0 eq
randomized42: 0 lt; 598 gt; 0 eq
randomized93: 0 lt; 576 gt; 0 eq
randomized11111: 0 lt; 575 gt; 0 eq

======= heapq.merge ======
No overlap: 524 lt; 0 gt; 524 eq
Interleaved: 518 lt; 0 gt; 518 eq
randomized42: 574 lt; 0 gt; 574 eq
randomized93: 580 lt; 0 gt; 580 eq
randomized11111: 583 lt; 0 gt; 583 eq

==== multimerge.merge ====
No overlap: 256 lt; 0 gt; 0 eq
Interleaved: 480 lt; 0 gt; 0 eq
randomized42: 443 lt; 0 gt; 0 eq
randomized93: 475 lt; 0 gt; 0 eq
randomized11111: 479 lt; 0 gt; 0 eq

K=16 N=16
======= siftdown ======
No overlap: 0 lt; 311 gt; 0 eq
Interleaved: 0 lt; 1,560 gt; 0 eq
randomized42: 0 lt; 1,306 gt; 0 eq
randomized93: 0 lt; 1,277 gt; 0 eq
randomized11111: 0 lt; 1,232 gt; 0 eq

======= heapq.merge ======
No overlap: 1,044 lt; 0 gt; 1,044 eq
Interleaved: 1,028 lt; 0 gt; 1,028 eq
randomized42: 1,223 lt; 0 gt; 1,223 eq
randomized93: 1,206 lt; 0 gt; 1,206 eq
randomized11111: 1,187 lt; 0 gt; 1,187 eq

==== multimerge.merge ====
No overlap: 512 lt; 0 gt; 0 eq
Interleaved: 992 lt; 0 gt; 0 eq
randomized42: 954 lt; 0 gt; 0 eq
randomized93: 986 lt; 0 gt; 0 eq
randomized11111: 948 lt; 0 gt; 0 eq

K=16 N=32
======= siftdown ======
No overlap: 0 lt; 551 gt; 0 eq
Interleaved: 0 lt; 3,150 gt; 0 eq
randomized42: 0 lt; 2,474 gt; 0 eq
randomized93: 0 lt; 2,630 gt; 0 eq
randomized11111: 0 lt; 2,545 gt; 0 eq

======= heapq.merge ======
No overlap: 2,084 lt; 0 gt; 2,084 eq
Interleaved: 2,052 lt; 0 gt; 2,052 eq
randomized42: 2,457 lt; 0 gt; 2,457 eq
randomized93: 2,512 lt; 0 gt; 2,512 eq
randomized11111: 2,495 lt; 0 gt; 2,495 eq

==== multimerge.merge ====
No overlap: 1,024 lt; 0 gt; 0 eq
Interleaved: 2,016 lt; 0 gt; 0 eq
randomized42: 1,958 lt; 0 gt; 0 eq
randomized93: 1,993 lt; 0 gt; 0 eq
randomized11111: 1,978 lt; 0 gt; 0 eq

K=16 N=64
======= siftdown ======
No overlap: 0 lt; 1,031 gt; 0 eq
Interleaved: 0 lt; 6,329 gt; 0 eq
randomized42: 0 lt; 5,088 gt; 0 eq
randomized93: 0 lt; 5,364 gt; 0 eq
randomized11111: 0 lt; 5,324 gt; 0 eq

======= heapq.merge ======
No overlap: 4,164 lt; 0 gt; 4,164 eq
Interleaved: 4,103 lt; 0 gt; 4,103 eq
randomized42: 5,278 lt; 0 gt; 5,278 eq
randomized93: 4,995 lt; 0 gt; 4,995 eq
randomized11111: 5,120 lt; 0 gt; 5,120 eq

==== multimerge.merge ====
No overlap: 2,048 lt; 0 gt; 0 eq
Interleaved: 4,064 lt; 0 gt; 0 eq
randomized42: 4,063 lt; 0 gt; 0 eq
randomized93: 4,066 lt; 0 gt; 0 eq
randomized11111: 4,060 lt; 0 gt; 0 eq

K=16 N=128
======= siftdown ======
No overlap: 0 lt; 1,991 gt; 0 eq
Interleaved: 0 lt; 12,677 gt; 0 eq
randomized42: 0 lt; 9,714 gt; 0 eq
randomized93: 0 lt; 10,060 gt; 0 eq
randomized11111: 0 lt; 10,506 gt; 0 eq

======= heapq.merge ======
No overlap: 8,324 lt; 0 gt; 8,324 eq
Interleaved: 8,195 lt; 0 gt; 8,195 eq
randomized42: 10,538 lt; 0 gt; 10,538 eq
randomized93: 10,674 lt; 0 gt; 10,674 eq
randomized11111: 10,244 lt; 0 gt; 10,244 eq

==== multimerge.merge ====
No overlap: 4,096 lt; 0 gt; 0 eq
Interleaved: 8,160 lt; 0 gt; 0 eq
randomized42: 8,073 lt; 0 gt; 0 eq
randomized93: 8,132 lt; 0 gt; 0 eq
randomized11111: 8,129 lt; 0 gt; 0 eq

K=16 N=256
======= siftdown ======
No overlap: 0 lt; 3,911 gt; 0 eq
Interleaved: 0 lt; 25,383 gt; 0 eq
randomized42: 0 lt; 21,022 gt; 0 eq
randomized93: 0 lt; 20,891 gt; 0 eq
randomized11111: 0 lt; 19,187 gt; 0 eq

======= heapq.merge ======
No overlap: 16,644 lt; 0 gt; 16,644 eq
Interleaved: 16,388 lt; 0 gt; 16,388 eq
randomized42: 20,819 lt; 0 gt; 20,819 eq
randomized93: 20,894 lt; 0 gt; 20,894 eq
randomized11111: 21,514 lt; 0 gt; 21,514 eq

==== multimerge.merge ====
No overlap: 8,192 lt; 0 gt; 0 eq
Interleaved: 16,352 lt; 0 gt; 0 eq
randomized42: 16,289 lt; 0 gt; 0 eq
randomized93: 16,341 lt; 0 gt; 0 eq
randomized11111: 16,349 lt; 0 gt; 0 eq

K=16 N=512
======= siftdown ======
No overlap: 0 lt; 7,751 gt; 0 eq
Interleaved: 0 lt; 50,789 gt; 0 eq
randomized42: 0 lt; 39,798 gt; 0 eq
randomized93: 0 lt; 43,367 gt; 0 eq
randomized11111: 0 lt; 42,524 gt; 0 eq

======= heapq.merge ======
No overlap: 33,284 lt; 0 gt; 33,284 eq
Interleaved: 32,773 lt; 0 gt; 32,773 eq
randomized42: 42,545 lt; 0 gt; 42,545 eq
randomized93: 40,754 lt; 0 gt; 40,754 eq
randomized11111: 41,205 lt; 0 gt; 41,205 eq

==== multimerge.merge ====
No overlap: 16,384 lt; 0 gt; 0 eq
Interleaved: 32,736 lt; 0 gt; 0 eq
randomized42: 32,302 lt; 0 gt; 0 eq
randomized93: 32,704 lt; 0 gt; 0 eq
randomized11111: 32,730 lt; 0 gt; 0 eq

K=32 N=1
======= siftdown ======
No overlap: 0 lt; 202 gt; 0 eq
Interleaved: 0 lt; 202 gt; 0 eq
randomized42: 0 lt; 185 gt; 0 eq
randomized93: 0 lt; 187 gt; 0 eq
randomized11111: 0 lt; 185 gt; 0 eq

======= heapq.merge ======
No overlap: 179 lt; 0 gt; 179 eq
Interleaved: 179 lt; 0 gt; 179 eq
randomized42: 140 lt; 0 gt; 140 eq
randomized93: 152 lt; 0 gt; 152 eq
randomized11111: 140 lt; 0 gt; 140 eq

==== multimerge.merge ====
No overlap: 80 lt; 0 gt; 0 eq
Interleaved: 80 lt; 0 gt; 0 eq
randomized42: 117 lt; 0 gt; 0 eq
randomized93: 119 lt; 0 gt; 0 eq
randomized11111: 120 lt; 0 gt; 0 eq

K=32 N=2
======= siftdown ======
No overlap: 0 lt; 263 gt; 0 eq
Interleaved: 0 lt; 463 gt; 0 eq
randomized42: 0 lt; 373 gt; 0 eq
randomized93: 0 lt; 396 gt; 0 eq
randomized11111: 0 lt; 402 gt; 0 eq

======= heapq.merge ======
No overlap: 364 lt; 0 gt; 364 eq
Interleaved: 338 lt; 0 gt; 338 eq
randomized42: 335 lt; 0 gt; 335 eq
randomized93: 308 lt; 0 gt; 308 eq
randomized11111: 325 lt; 0 gt; 325 eq

==== multimerge.merge ====
No overlap: 160 lt; 0 gt; 0 eq
Interleaved: 240 lt; 0 gt; 0 eq
randomized42: 247 lt; 0 gt; 0 eq
randomized93: 261 lt; 0 gt; 0 eq
randomized11111: 270 lt; 0 gt; 0 eq

K=32 N=4
======= siftdown ======
No overlap: 0 lt; 325 gt; 0 eq
Interleaved: 0 lt; 976 gt; 0 eq
randomized42: 0 lt; 788 gt; 0 eq
randomized93: 0 lt; 819 gt; 0 eq
randomized11111: 0 lt; 780 gt; 0 eq

======= heapq.merge ======
No overlap: 734 lt; 0 gt; 734 eq
Interleaved: 655 lt; 0 gt; 655 eq
randomized42: 657 lt; 0 gt; 657 eq
randomized93: 696 lt; 0 gt; 696 eq
randomized11111: 678 lt; 0 gt; 678 eq

==== multimerge.merge ====
No overlap: 320 lt; 0 gt; 0 eq
Interleaved: 560 lt; 0 gt; 0 eq
randomized42: 546 lt; 0 gt; 0 eq
randomized93: 572 lt; 0 gt; 0 eq
randomized11111: 571 lt; 0 gt; 0 eq

K=32 N=8
======= siftdown ======
No overlap: 0 lt; 449 gt; 0 eq
Interleaved: 0 lt; 2,011 gt; 0 eq
randomized42: 0 lt; 1,669 gt; 0 eq
randomized93: 0 lt; 1,655 gt; 0 eq
randomized11111: 0 lt; 1,609 gt; 0 eq

======= heapq.merge ======
No overlap: 1,474 lt; 0 gt; 1,474 eq
Interleaved: 1,298 lt; 0 gt; 1,298 eq
randomized42: 1,426 lt; 0 gt; 1,426 eq
randomized93: 1,466 lt; 0 gt; 1,466 eq
randomized11111: 1,432 lt; 0 gt; 1,432 eq

==== multimerge.merge ====
No overlap: 640 lt; 0 gt; 0 eq
Interleaved: 1,200 lt; 0 gt; 0 eq
randomized42: 1,200 lt; 0 gt; 0 eq
randomized93: 1,206 lt; 0 gt; 0 eq
randomized11111: 1,166 lt; 0 gt; 0 eq

K=32 N=16
======= siftdown ======
No overlap: 0 lt; 697 gt; 0 eq
Interleaved: 0 lt; 4,092 gt; 0 eq
randomized42: 0 lt; 3,197 gt; 0 eq
randomized93: 0 lt; 3,492 gt; 0 eq
randomized11111: 0 lt; 3,461 gt; 0 eq

======= heapq.merge ======
No overlap: 2,954 lt; 0 gt; 2,954 eq
Interleaved: 2,577 lt; 0 gt; 2,577 eq
randomized42: 3,003 lt; 0 gt; 3,003 eq
randomized93: 3,065 lt; 0 gt; 3,065 eq
randomized11111: 2,996 lt; 0 gt; 2,996 eq

==== multimerge.merge ====
No overlap: 1,280 lt; 0 gt; 0 eq
Interleaved: 2,480 lt; 0 gt; 0 eq
randomized42: 2,378 lt; 0 gt; 0 eq
randomized93: 2,475 lt; 0 gt; 0 eq
randomized11111: 2,436 lt; 0 gt; 0 eq

K=32 N=32
======= siftdown ======
No overlap: 0 lt; 1,193 gt; 0 eq
Interleaved: 0 lt; 8,242 gt; 0 eq
randomized42: 0 lt; 6,651 gt; 0 eq
randomized93: 0 lt; 6,729 gt; 0 eq
randomized11111: 0 lt; 6,887 gt; 0 eq

======= heapq.merge ======
No overlap: 5,914 lt; 0 gt; 5,914 eq
Interleaved: 5,134 lt; 0 gt; 5,134 eq
randomized42: 6,315 lt; 0 gt; 6,315 eq
randomized93: 6,143 lt; 0 gt; 6,143 eq
randomized11111: 6,245 lt; 0 gt; 6,245 eq

==== multimerge.merge ====
No overlap: 2,560 lt; 0 gt; 0 eq
Interleaved: 5,040 lt; 0 gt; 0 eq
randomized42: 4,999 lt; 0 gt; 0 eq
randomized93: 4,944 lt; 0 gt; 0 eq
randomized11111: 5,002 lt; 0 gt; 0 eq

K=32 N=64
======= siftdown ======
No overlap: 0 lt; 2,185 gt; 0 eq
Interleaved: 0 lt; 16,540 gt; 0 eq
randomized42: 0 lt; 13,448 gt; 0 eq
randomized93: 0 lt; 13,470 gt; 0 eq
randomized11111: 0 lt; 13,589 gt; 0 eq

======= heapq.merge ======
No overlap: 11,834 lt; 0 gt; 11,834 eq
Interleaved: 10,258 lt; 0 gt; 10,258 eq
randomized42: 12,657 lt; 0 gt; 12,657 eq
randomized93: 12,821 lt; 0 gt; 12,821 eq
randomized11111: 12,608 lt; 0 gt; 12,608 eq

==== multimerge.merge ====
No overlap: 5,120 lt; 0 gt; 0 eq
Interleaved: 10,160 lt; 0 gt; 0 eq
randomized42: 10,027 lt; 0 gt; 0 eq
randomized93: 10,097 lt; 0 gt; 0 eq
randomized11111: 9,935 lt; 0 gt; 0 eq

K=32 N=128
======= siftdown ======
No overlap: 0 lt; 4,169 gt; 0 eq
Interleaved: 0 lt; 33,140 gt; 0 eq
randomized42: 0 lt; 27,739 gt; 0 eq
randomized93: 0 lt; 27,424 gt; 0 eq
randomized11111: 0 lt; 27,902 gt; 0 eq

======= heapq.merge ======
No overlap: 23,674 lt; 0 gt; 23,674 eq
Interleaved: 20,493 lt; 0 gt; 20,493 eq
randomized42: 25,118 lt; 0 gt; 25,118 eq
randomized93: 25,464 lt; 0 gt; 25,464 eq
randomized11111: 25,215 lt; 0 gt; 25,215 eq

==== multimerge.merge ====
No overlap: 10,240 lt; 0 gt; 0 eq
Interleaved: 20,400 lt; 0 gt; 0 eq
randomized42: 20,300 lt; 0 gt; 0 eq
randomized93: 20,231 lt; 0 gt; 0 eq
randomized11111: 20,297 lt; 0 gt; 0 eq

K=32 N=256
======= siftdown ======
No overlap: 0 lt; 8,137 gt; 0 eq
Interleaved: 0 lt; 66,344 gt; 0 eq
randomized42: 0 lt; 55,720 gt; 0 eq
randomized93: 0 lt; 56,102 gt; 0 eq
randomized11111: 0 lt; 55,092 gt; 0 eq

======= heapq.merge ======
No overlap: 47,354 lt; 0 gt; 47,354 eq
Interleaved: 40,979 lt; 0 gt; 40,979 eq
randomized42: 50,807 lt; 0 gt; 50,807 eq
randomized93: 51,189 lt; 0 gt; 51,189 eq
randomized11111: 51,396 lt; 0 gt; 51,396 eq

==== multimerge.merge ====
No overlap: 20,480 lt; 0 gt; 0 eq
Interleaved: 40,880 lt; 0 gt; 0 eq
randomized42: 40,645 lt; 0 gt; 0 eq
randomized93: 40,838 lt; 0 gt; 0 eq
randomized11111: 40,871 lt; 0 gt; 0 eq

K=32 N=512
======= siftdown ======
No overlap: 0 lt; 16,073 gt; 0 eq
Interleaved: 0 lt; 132,727 gt; 0 eq
randomized42: 0 lt; 108,008 gt; 0 eq
randomized93: 0 lt; 113,471 gt; 0 eq
randomized11111: 0 lt; 113,922 gt; 0 eq

======= heapq.merge ======
No overlap: 94,714 lt; 0 gt; 94,714 eq
Interleaved: 81,933 lt; 0 gt; 81,933 eq
randomized42: 104,910 lt; 0 gt; 104,910 eq
randomized93: 101,291 lt; 0 gt; 101,291 eq
randomized11111: 101,198 lt; 0 gt; 101,198 eq

==== multimerge.merge ====
No overlap: 40,960 lt; 0 gt; 0 eq
Interleaved: 81,840 lt; 0 gt; 0 eq
randomized42: 81,733 lt; 0 gt; 0 eq
randomized93: 81,771 lt; 0 gt; 0 eq
randomized11111: 81,813 lt; 0 gt; 0 eq

K=64 N=1
======= siftdown ======
No overlap: 0 lt; 525 gt; 0 eq
Interleaved: 0 lt; 525 gt; 0 eq
randomized42: 0 lt; 477 gt; 0 eq
randomized93: 0 lt; 483 gt; 0 eq
randomized11111: 0 lt; 469 gt; 0 eq

======= heapq.merge ======
No overlap: 421 lt; 0 gt; 421 eq
Interleaved: 421 lt; 0 gt; 421 eq
randomized42: 368 lt; 0 gt; 368 eq
randomized93: 357 lt; 0 gt; 357 eq
randomized11111: 357 lt; 0 gt; 357 eq

==== multimerge.merge ====
No overlap: 192 lt; 0 gt; 0 eq
Interleaved: 192 lt; 0 gt; 0 eq
randomized42: 292 lt; 0 gt; 0 eq
randomized93: 306 lt; 0 gt; 0 eq
randomized11111: 297 lt; 0 gt; 0 eq

K=64 N=2
======= siftdown ======
No overlap: 0 lt; 650 gt; 0 eq
Interleaved: 0 lt; 1,170 gt; 0 eq
randomized42: 0 lt; 1,013 gt; 0 eq
randomized93: 0 lt; 996 gt; 0 eq
randomized11111: 0 lt; 974 gt; 0 eq

======= heapq.merge ======
No overlap: 899 lt; 0 gt; 899 eq
Interleaved: 808 lt; 0 gt; 808 eq
randomized42: 763 lt; 0 gt; 763 eq
randomized93: 789 lt; 0 gt; 789 eq
randomized11111: 778 lt; 0 gt; 778 eq

==== multimerge.merge ====
No overlap: 384 lt; 0 gt; 0 eq
Interleaved: 576 lt; 0 gt; 0 eq
randomized42: 642 lt; 0 gt; 0 eq
randomized93: 653 lt; 0 gt; 0 eq
randomized11111: 648 lt; 0 gt; 0 eq

K=64 N=4
======= siftdown ======
No overlap: 0 lt; 776 gt; 0 eq
Interleaved: 0 lt; 2,457 gt; 0 eq
randomized42: 0 lt; 2,139 gt; 0 eq
randomized93: 0 lt; 2,072 gt; 0 eq
randomized11111: 0 lt; 2,038 gt; 0 eq

======= heapq.merge ======
No overlap: 1,855 lt; 0 gt; 1,855 eq
Interleaved: 1,571 lt; 0 gt; 1,571 eq
randomized42: 1,662 lt; 0 gt; 1,662 eq
randomized93: 1,724 lt; 0 gt; 1,724 eq
randomized11111: 1,656 lt; 0 gt; 1,656 eq

==== multimerge.merge ====
No overlap: 768 lt; 0 gt; 0 eq
Interleaved: 1,344 lt; 0 gt; 0 eq
randomized42: 1,388 lt; 0 gt; 0 eq
randomized93: 1,414 lt; 0 gt; 0 eq
randomized11111: 1,377 lt; 0 gt; 0 eq

K=64 N=8
======= siftdown ======
No overlap: 0 lt; 1,028 gt; 0 eq
Interleaved: 0 lt; 5,003 gt; 0 eq
randomized42: 0 lt; 4,228 gt; 0 eq
randomized93: 0 lt; 4,331 gt; 0 eq
randomized11111: 0 lt; 4,176 gt; 0 eq

======= heapq.merge ======
No overlap: 3,767 lt; 0 gt; 3,767 eq
Interleaved: 3,115 lt; 0 gt; 3,115 eq
randomized42: 3,441 lt; 0 gt; 3,441 eq
randomized93: 3,468 lt; 0 gt; 3,468 eq
randomized11111: 3,515 lt; 0 gt; 3,515 eq

==== multimerge.merge ====
No overlap: 1,536 lt; 0 gt; 0 eq
Interleaved: 2,880 lt; 0 gt; 0 eq
randomized42: 2,856 lt; 0 gt; 0 eq
randomized93: 2,892 lt; 0 gt; 0 eq
randomized11111: 2,855 lt; 0 gt; 0 eq

K=64 N=16
======= siftdown ======
No overlap: 0 lt; 1,532 gt; 0 eq
Interleaved: 0 lt; 10,181 gt; 0 eq
randomized42: 0 lt; 8,360 gt; 0 eq
randomized93: 0 lt; 8,240 gt; 0 eq
randomized11111: 0 lt; 8,644 gt; 0 eq

======= heapq.merge ======
No overlap: 7,591 lt; 0 gt; 7,591 eq
Interleaved: 6,185 lt; 0 gt; 6,185 eq
randomized42: 7,264 lt; 0 gt; 7,264 eq
randomized93: 7,345 lt; 0 gt; 7,345 eq
randomized11111: 7,294 lt; 0 gt; 7,294 eq

==== multimerge.merge ====
No overlap: 3,072 lt; 0 gt; 0 eq
Interleaved: 5,952 lt; 0 gt; 0 eq
randomized42: 5,912 lt; 0 gt; 0 eq
randomized93: 5,907 lt; 0 gt; 0 eq
randomized11111: 5,935 lt; 0 gt; 0 eq

K=64 N=32
======= siftdown ======
No overlap: 0 lt; 2,540 gt; 0 eq
Interleaved: 0 lt; 20,467 gt; 0 eq
randomized42: 0 lt; 16,910 gt; 0 eq
randomized93: 0 lt; 16,901 gt; 0 eq
randomized11111: 0 lt; 16,933 gt; 0 eq

======= heapq.merge ======
No overlap: 15,239 lt; 0 gt; 15,239 eq
Interleaved: 12,325 lt; 0 gt; 12,325 eq
randomized42: 14,816 lt; 0 gt; 14,816 eq
randomized93: 14,975 lt; 0 gt; 14,975 eq
randomized11111: 14,632 lt; 0 gt; 14,632 eq

==== multimerge.merge ====
No overlap: 6,144 lt; 0 gt; 0 eq
Interleaved: 12,096 lt; 0 gt; 0 eq
randomized42: 11,943 lt; 0 gt; 0 eq
randomized93: 11,965 lt; 0 gt; 0 eq
randomized11111: 11,991 lt; 0 gt; 0 eq

K=64 N=64
======= siftdown ======
No overlap: 0 lt; 4,556 gt; 0 eq
Interleaved: 0 lt; 41,068 gt; 0 eq
randomized42: 0 lt; 34,140 gt; 0 eq
randomized93: 0 lt; 34,350 gt; 0 eq
randomized11111: 0 lt; 34,799 gt; 0 eq

======= heapq.merge ======
No overlap: 30,535 lt; 0 gt; 30,535 eq
Interleaved: 24,618 lt; 0 gt; 24,618 eq
randomized42: 29,768 lt; 0 gt; 29,768 eq
randomized93: 30,032 lt; 0 gt; 30,032 eq
randomized11111: 29,886 lt; 0 gt; 29,886 eq

==== multimerge.merge ====
No overlap: 12,288 lt; 0 gt; 0 eq
Interleaved: 24,384 lt; 0 gt; 0 eq
randomized42: 24,059 lt; 0 gt; 0 eq
randomized93: 24,240 lt; 0 gt; 0 eq
randomized11111: 24,228 lt; 0 gt; 0 eq

K=64 N=128
======= siftdown ======
No overlap: 0 lt; 8,588 gt; 0 eq
Interleaved: 0 lt; 82,239 gt; 0 eq
randomized42: 0 lt; 70,357 gt; 0 eq
randomized93: 0 lt; 69,086 gt; 0 eq
randomized11111: 0 lt; 71,218 gt; 0 eq

======= heapq.merge ======
No overlap: 61,127 lt; 0 gt; 61,127 eq
Interleaved: 49,185 lt; 0 gt; 49,185 eq
randomized42: 59,788 lt; 0 gt; 59,788 eq
randomized93: 60,616 lt; 0 gt; 60,616 eq
randomized11111: 59,663 lt; 0 gt; 59,663 eq

==== multimerge.merge ====
No overlap: 24,576 lt; 0 gt; 0 eq
Interleaved: 48,960 lt; 0 gt; 0 eq
randomized42: 48,597 lt; 0 gt; 0 eq
randomized93: 48,927 lt; 0 gt; 0 eq
randomized11111: 49,000 lt; 0 gt; 0 eq

K=64 N=256
======= siftdown ======
No overlap: 0 lt; 16,652 gt; 0 eq
Interleaved: 0 lt; 164,590 gt; 0 eq
randomized42: 0 lt; 140,428 gt; 0 eq
randomized93: 0 lt; 139,811 gt; 0 eq
randomized11111: 0 lt; 139,298 gt; 0 eq

======= heapq.merge ======
No overlap: 122,311 lt; 0 gt; 122,311 eq
Interleaved: 98,344 lt; 0 gt; 98,344 eq
randomized42: 120,261 lt; 0 gt; 120,261 eq
randomized93: 120,960 lt; 0 gt; 120,960 eq
randomized11111: 121,781 lt; 0 gt; 121,781 eq

==== multimerge.merge ====
No overlap: 49,152 lt; 0 gt; 0 eq
Interleaved: 98,112 lt; 0 gt; 0 eq
randomized42: 97,809 lt; 0 gt; 0 eq
randomized93: 97,980 lt; 0 gt; 0 eq
randomized11111: 98,063 lt; 0 gt; 0 eq

K=64 N=512
======= siftdown ======
No overlap: 0 lt; 32,780 gt; 0 eq
Interleaved: 0 lt; 329,303 gt; 0 eq
randomized42: 0 lt; 280,617 gt; 0 eq
randomized93: 0 lt; 275,805 gt; 0 eq
randomized11111: 0 lt; 277,319 gt; 0 eq

======= heapq.merge ======
No overlap: 244,679 lt; 0 gt; 244,679 eq
Interleaved: 196,647 lt; 0 gt; 196,647 eq
randomized42: 241,557 lt; 0 gt; 241,557 eq
randomized93: 245,416 lt; 0 gt; 245,416 eq
randomized11111: 243,690 lt; 0 gt; 243,690 eq

==== multimerge.merge ====
No overlap: 98,304 lt; 0 gt; 0 eq
Interleaved: 196,416 lt; 0 gt; 0 eq
randomized42: 196,328 lt; 0 gt; 0 eq
randomized93: 196,390 lt; 0 gt; 0 eq
randomized11111: 196,254 lt; 0 gt; 0 eq

K=128 N=1
======= siftdown ======
No overlap: 0 lt; 1,294 gt; 0 eq
Interleaved: 0 lt; 1,294 gt; 0 eq
randomized42: 0 lt; 1,207 gt; 0 eq
randomized93: 0 lt; 1,227 gt; 0 eq
randomized11111: 0 lt; 1,166 gt; 0 eq

======= heapq.merge ======
No overlap: 967 lt; 0 gt; 967 eq
Interleaved: 967 lt; 0 gt; 967 eq
randomized42: 836 lt; 0 gt; 836 eq
randomized93: 863 lt; 0 gt; 863 eq
randomized11111: 826 lt; 0 gt; 826 eq

==== multimerge.merge ====
No overlap: 448 lt; 0 gt; 0 eq
Interleaved: 448 lt; 0 gt; 0 eq
randomized42: 725 lt; 0 gt; 0 eq
randomized93: 722 lt; 0 gt; 0 eq
randomized11111: 728 lt; 0 gt; 0 eq

K=128 N=2
======= siftdown ======
No overlap: 0 lt; 1,547 gt; 0 eq
Interleaved: 0 lt; 2,844 gt; 0 eq
randomized42: 0 lt; 2,528 gt; 0 eq
randomized93: 0 lt; 2,477 gt; 0 eq
randomized11111: 0 lt; 2,386 gt; 0 eq

======= heapq.merge ======
No overlap: 2,155 lt; 0 gt; 2,155 eq
Interleaved: 1,884 lt; 0 gt; 1,884 eq
randomized42: 1,816 lt; 0 gt; 1,816 eq
randomized93: 1,888 lt; 0 gt; 1,888 eq
randomized11111: 1,796 lt; 0 gt; 1,796 eq

==== multimerge.merge ====
No overlap: 896 lt; 0 gt; 0 eq
Interleaved: 1,344 lt; 0 gt; 0 eq
randomized42: 1,540 lt; 0 gt; 0 eq
randomized93: 1,593 lt; 0 gt; 0 eq
randomized11111: 1,536 lt; 0 gt; 0 eq

K=128 N=4
======= siftdown ======
No overlap: 0 lt; 1,801 gt; 0 eq
Interleaved: 0 lt; 5,917 gt; 0 eq
randomized42: 0 lt; 5,222 gt; 0 eq
randomized93: 0 lt; 5,111 gt; 0 eq
randomized11111: 0 lt; 4,861 gt; 0 eq

======= heapq.merge ======
No overlap: 4,531 lt; 0 gt; 4,531 eq
Interleaved: 3,668 lt; 0 gt; 3,668 eq
randomized42: 3,829 lt; 0 gt; 3,829 eq
randomized93: 3,924 lt; 0 gt; 3,924 eq
randomized11111: 3,823 lt; 0 gt; 3,823 eq

==== multimerge.merge ====
No overlap: 1,792 lt; 0 gt; 0 eq
Interleaved: 3,136 lt; 0 gt; 0 eq
randomized42: 3,255 lt; 0 gt; 0 eq
randomized93: 3,252 lt; 0 gt; 0 eq
randomized11111: 3,235 lt; 0 gt; 0 eq

K=128 N=8
======= siftdown ======
No overlap: 0 lt; 2,309 gt; 0 eq
Interleaved: 0 lt; 12,083 gt; 0 eq
randomized42: 0 lt; 10,414 gt; 0 eq
randomized93: 0 lt; 10,334 gt; 0 eq
randomized11111: 0 lt; 10,158 gt; 0 eq

======= heapq.merge ======
No overlap: 9,283 lt; 0 gt; 9,283 eq
Interleaved: 7,274 lt; 0 gt; 7,274 eq
randomized42: 8,077 lt; 0 gt; 8,077 eq
randomized93: 8,013 lt; 0 gt; 8,013 eq
randomized11111: 8,299 lt; 0 gt; 8,299 eq

==== multimerge.merge ====
No overlap: 3,584 lt; 0 gt; 0 eq
Interleaved: 6,720 lt; 0 gt; 0 eq
randomized42: 6,819 lt; 0 gt; 0 eq
randomized93: 6,796 lt; 0 gt; 0 eq
randomized11111: 6,820 lt; 0 gt; 0 eq

K=128 N=16
======= siftdown ======
No overlap: 0 lt; 3,325 gt; 0 eq
Interleaved: 0 lt; 24,353 gt; 0 eq
randomized42: 0 lt; 20,942 gt; 0 eq
randomized93: 0 lt; 21,184 gt; 0 eq
randomized11111: 0 lt; 20,484 gt; 0 eq

======= heapq.merge ======
No overlap: 18,787 lt; 0 gt; 18,787 eq
Interleaved: 14,428 lt; 0 gt; 14,428 eq
randomized42: 16,635 lt; 0 gt; 16,635 eq
randomized93: 16,560 lt; 0 gt; 16,560 eq
randomized11111: 16,568 lt; 0 gt; 16,568 eq

==== multimerge.merge ====
No overlap: 7,168 lt; 0 gt; 0 eq
Interleaved: 13,888 lt; 0 gt; 0 eq
randomized42: 13,824 lt; 0 gt; 0 eq
randomized93: 13,900 lt; 0 gt; 0 eq
randomized11111: 13,791 lt; 0 gt; 0 eq

K=128 N=32
======= siftdown ======
No overlap: 0 lt; 5,357 gt; 0 eq
Interleaved: 0 lt; 49,021 gt; 0 eq
randomized42: 0 lt; 41,175 gt; 0 eq
randomized93: 0 lt; 41,736 gt; 0 eq
randomized11111: 0 lt; 42,183 gt; 0 eq

======= heapq.merge ======
No overlap: 37,795 lt; 0 gt; 37,795 eq
Interleaved: 28,761 lt; 0 gt; 28,761 eq
randomized42: 34,260 lt; 0 gt; 34,260 eq
randomized93: 34,066 lt; 0 gt; 34,066 eq
randomized11111: 33,898 lt; 0 gt; 33,898 eq

==== multimerge.merge ====
No overlap: 14,336 lt; 0 gt; 0 eq
Interleaved: 28,224 lt; 0 gt; 0 eq
randomized42: 28,061 lt; 0 gt; 0 eq
randomized93: 28,092 lt; 0 gt; 0 eq
randomized11111: 28,163 lt; 0 gt; 0 eq

K=128 N=64
======= siftdown ======
No overlap: 0 lt; 9,421 gt; 0 eq
Interleaved: 0 lt; 98,276 gt; 0 eq
randomized42: 0 lt; 84,170 gt; 0 eq
randomized93: 0 lt; 84,857 gt; 0 eq
randomized11111: 0 lt; 86,404 gt; 0 eq

======= heapq.merge ======
No overlap: 75,811 lt; 0 gt; 75,811 eq
Interleaved: 57,436 lt; 0 gt; 57,436 eq
randomized42: 68,621 lt; 0 gt; 68,621 eq
randomized93: 68,447 lt; 0 gt; 68,447 eq
randomized11111: 67,888 lt; 0 gt; 67,888 eq

==== multimerge.merge ====
No overlap: 28,672 lt; 0 gt; 0 eq
Interleaved: 56,896 lt; 0 gt; 0 eq
randomized42: 56,520 lt; 0 gt; 0 eq
randomized93: 56,838 lt; 0 gt; 0 eq
randomized11111: 56,973 lt; 0 gt; 0 eq

K=128 N=128
======= siftdown ======
No overlap: 0 lt; 17,549 gt; 0 eq
Interleaved: 0 lt; 196,811 gt; 0 eq
randomized42: 0 lt; 168,182 gt; 0 eq
randomized93: 0 lt; 172,624 gt; 0 eq
randomized11111: 0 lt; 171,765 gt; 0 eq

======= heapq.merge ======
No overlap: 151,843 lt; 0 gt; 151,843 eq
Interleaved: 114,775 lt; 0 gt; 114,775 eq
randomized42: 138,921 lt; 0 gt; 138,921 eq
randomized93: 136,284 lt; 0 gt; 136,284 eq
randomized11111: 137,002 lt; 0 gt; 137,002 eq

==== multimerge.merge ====
No overlap: 57,344 lt; 0 gt; 0 eq
Interleaved: 114,240 lt; 0 gt; 0 eq
randomized42: 114,117 lt; 0 gt; 0 eq
randomized93: 113,996 lt; 0 gt; 0 eq
randomized11111: 114,002 lt; 0 gt; 0 eq

K=128 N=256
======= siftdown ======
No overlap: 0 lt; 33,805 gt; 0 eq
Interleaved: 0 lt; 393,864 gt; 0 eq
randomized42: 0 lt; 345,650 gt; 0 eq
randomized93: 0 lt; 332,826 gt; 0 eq
randomized11111: 0 lt; 342,151 gt; 0 eq

======= heapq.merge ======
No overlap: 303,907 lt; 0 gt; 303,907 eq
Interleaved: 229,465 lt; 0 gt; 229,465 eq
randomized42: 274,503 lt; 0 gt; 274,503 eq
randomized93: 281,736 lt; 0 gt; 281,736 eq
randomized11111: 275,666 lt; 0 gt; 275,666 eq

==== multimerge.merge ====
No overlap: 114,688 lt; 0 gt; 0 eq
Interleaved: 228,928 lt; 0 gt; 0 eq
randomized42: 228,758 lt; 0 gt; 0 eq
randomized93: 228,634 lt; 0 gt; 0 eq
randomized11111: 228,169 lt; 0 gt; 0 eq

K=128 N=512
======= siftdown ======
No overlap: 0 lt; 66,317 gt; 0 eq
Interleaved: 0 lt; 787,953 gt; 0 eq
randomized42: 0 lt; 676,064 gt; 0 eq
randomized93: 0 lt; 681,008 gt; 0 eq
randomized11111: 0 lt; 677,788 gt; 0 eq

======= heapq.merge ======
No overlap: 608,035 lt; 0 gt; 608,035 eq
Interleaved: 458,841 lt; 0 gt; 458,841 eq
randomized42: 559,923 lt; 0 gt; 559,923 eq
randomized93: 555,291 lt; 0 gt; 555,291 eq
randomized11111: 555,748 lt; 0 gt; 555,748 eq

==== multimerge.merge ====
No overlap: 229,376 lt; 0 gt; 0 eq
Interleaved: 458,304 lt; 0 gt; 0 eq
randomized42: 457,448 lt; 0 gt; 0 eq
randomized93: 458,089 lt; 0 gt; 0 eq
randomized11111: 455,030 lt; 0 gt; 0 eq

K=256 N=1
======= siftdown ======
No overlap: 0 lt; 3,106 gt; 0 eq
Interleaved: 0 lt; 3,106 gt; 0 eq
randomized42: 0 lt; 2,906 gt; 0 eq
randomized93: 0 lt; 2,865 gt; 0 eq
randomized11111: 0 lt; 2,855 gt; 0 eq

======= heapq.merge ======
No overlap: 2,230 lt; 0 gt; 2,230 eq
Interleaved: 2,230 lt; 0 gt; 2,230 eq
randomized42: 1,958 lt; 0 gt; 1,958 eq
randomized93: 1,973 lt; 0 gt; 1,973 eq
randomized11111: 1,964 lt; 0 gt; 1,964 eq

==== multimerge.merge ====
No overlap: 1,024 lt; 0 gt; 0 eq
Interleaved: 1,024 lt; 0 gt; 0 eq
randomized42: 1,680 lt; 0 gt; 0 eq
randomized93: 1,734 lt; 0 gt; 0 eq
randomized11111: 1,678 lt; 0 gt; 0 eq

K=256 N=2
======= siftdown ======
No overlap: 0 lt; 3,615 gt; 0 eq
Interleaved: 0 lt; 6,681 gt; 0 eq
randomized42: 0 lt; 5,990 gt; 0 eq
randomized93: 0 lt; 6,027 gt; 0 eq
randomized11111: 0 lt; 5,808 gt; 0 eq

======= heapq.merge ======
No overlap: 5,112 lt; 0 gt; 5,112 eq
Interleaved: 4,290 lt; 0 gt; 4,290 eq
randomized42: 4,186 lt; 0 gt; 4,186 eq
randomized93: 4,224 lt; 0 gt; 4,224 eq
randomized11111: 4,146 lt; 0 gt; 4,146 eq

==== multimerge.merge ====
No overlap: 2,048 lt; 0 gt; 0 eq
Interleaved: 3,072 lt; 0 gt; 0 eq
randomized42: 3,601 lt; 0 gt; 0 eq
randomized93: 3,651 lt; 0 gt; 0 eq
randomized11111: 3,621 lt; 0 gt; 0 eq

K=256 N=4
======= siftdown ======
No overlap: 0 lt; 4,125 gt; 0 eq
Interleaved: 0 lt; 13,874 gt; 0 eq
randomized42: 0 lt; 12,181 gt; 0 eq
randomized93: 0 lt; 12,268 gt; 0 eq
randomized11111: 0 lt; 12,115 gt; 0 eq

======= heapq.merge ======
No overlap: 10,876 lt; 0 gt; 10,876 eq
Interleaved: 8,388 lt; 0 gt; 8,388 eq
randomized42: 8,795 lt; 0 gt; 8,795 eq
randomized93: 8,719 lt; 0 gt; 8,719 eq
randomized11111: 8,894 lt; 0 gt; 8,894 eq

==== multimerge.merge ====
No overlap: 4,096 lt; 0 gt; 0 eq
Interleaved: 7,168 lt; 0 gt; 0 eq
randomized42: 7,572 lt; 0 gt; 0 eq
randomized93: 7,554 lt; 0 gt; 0 eq
randomized11111: 7,655 lt; 0 gt; 0 eq

K=256 N=8
======= siftdown ======
No overlap: 0 lt; 5,145 gt; 0 eq
Interleaved: 0 lt; 28,209 gt; 0 eq
randomized42: 0 lt; 24,728 gt; 0 eq
randomized93: 0 lt; 24,791 gt; 0 eq
randomized11111: 0 lt; 24,407 gt; 0 eq

======= heapq.merge ======
No overlap: 22,404 lt; 0 gt; 22,404 eq
Interleaved: 16,572 lt; 0 gt; 16,572 eq
randomized42: 18,238 lt; 0 gt; 18,238 eq
randomized93: 18,073 lt; 0 gt; 18,073 eq
randomized11111: 18,143 lt; 0 gt; 18,143 eq

==== multimerge.merge ====
No overlap: 8,192 lt; 0 gt; 0 eq
Interleaved: 15,360 lt; 0 gt; 0 eq
randomized42: 15,497 lt; 0 gt; 0 eq
randomized93: 15,638 lt; 0 gt; 0 eq
randomized11111: 15,542 lt; 0 gt; 0 eq

K=256 N=16
======= siftdown ======
No overlap: 0 lt; 7,185 gt; 0 eq
Interleaved: 0 lt; 56,904 gt; 0 eq
randomized42: 0 lt; 49,950 gt; 0 eq
randomized93: 0 lt; 49,181 gt; 0 eq
randomized11111: 0 lt; 49,681 gt; 0 eq

======= heapq.merge ======
No overlap: 45,460 lt; 0 gt; 45,460 eq
Interleaved: 32,985 lt; 0 gt; 32,985 eq
randomized42: 37,634 lt; 0 gt; 37,634 eq
randomized93: 37,881 lt; 0 gt; 37,881 eq
randomized11111: 37,549 lt; 0 gt; 37,549 eq

==== multimerge.merge ====
No overlap: 16,384 lt; 0 gt; 0 eq
Interleaved: 31,744 lt; 0 gt; 0 eq
randomized42: 31,908 lt; 0 gt; 0 eq
randomized93: 31,828 lt; 0 gt; 0 eq
randomized11111: 31,779 lt; 0 gt; 0 eq

K=256 N=32
======= siftdown ======
No overlap: 0 lt; 11,265 gt; 0 eq
Interleaved: 0 lt; 114,221 gt; 0 eq
randomized42: 0 lt; 99,326 gt; 0 eq
randomized93: 0 lt; 99,820 gt; 0 eq
randomized11111: 0 lt; 100,822 gt; 0 eq

======= heapq.merge ======
No overlap: 91,572 lt; 0 gt; 91,572 eq
Interleaved: 65,759 lt; 0 gt; 65,759 eq
randomized42: 76,009 lt; 0 gt; 76,009 eq
randomized93: 76,231 lt; 0 gt; 76,231 eq
randomized11111: 75,974 lt; 0 gt; 75,974 eq

==== multimerge.merge ====
No overlap: 32,768 lt; 0 gt; 0 eq
Interleaved: 64,512 lt; 0 gt; 0 eq
randomized42: 64,131 lt; 0 gt; 0 eq
randomized93: 64,409 lt; 0 gt; 0 eq
randomized11111: 64,451 lt; 0 gt; 0 eq

K=256 N=64
======= siftdown ======
No overlap: 0 lt; 19,425 gt; 0 eq
Interleaved: 0 lt; 229,122 gt; 0 eq
randomized42: 0 lt; 200,253 gt; 0 eq
randomized93: 0 lt; 201,145 gt; 0 eq
randomized11111: 0 lt; 201,268 gt; 0 eq

======= heapq.merge ======
No overlap: 183,796 lt; 0 gt; 183,796 eq
Interleaved: 131,265 lt; 0 gt; 131,265 eq
randomized42: 153,930 lt; 0 gt; 153,930 eq
randomized93: 154,075 lt; 0 gt; 154,075 eq
randomized11111: 154,056 lt; 0 gt; 154,056 eq

==== multimerge.merge ====
No overlap: 65,536 lt; 0 gt; 0 eq
Interleaved: 130,048 lt; 0 gt; 0 eq
randomized42: 129,671 lt; 0 gt; 0 eq
randomized93: 129,775 lt; 0 gt; 0 eq
randomized11111: 129,857 lt; 0 gt; 0 eq

K=256 N=128
======= siftdown ======
No overlap: 0 lt; 35,745 gt; 0 eq
Interleaved: 0 lt; 458,706 gt; 0 eq
randomized42: 0 lt; 405,386 gt; 0 eq
randomized93: 0 lt; 399,195 gt; 0 eq
randomized11111: 0 lt; 400,437 gt; 0 eq

======= heapq.merge ======
No overlap: 368,244 lt; 0 gt; 368,244 eq
Interleaved: 262,332 lt; 0 gt; 262,332 eq
randomized42: 307,849 lt; 0 gt; 307,849 eq
randomized93: 311,932 lt; 0 gt; 311,932 eq
randomized11111: 310,779 lt; 0 gt; 310,779 eq

==== multimerge.merge ====
No overlap: 131,072 lt; 0 gt; 0 eq
Interleaved: 261,120 lt; 0 gt; 0 eq
randomized42: 260,369 lt; 0 gt; 0 eq
randomized93: 260,057 lt; 0 gt; 0 eq
randomized11111: 260,250 lt; 0 gt; 0 eq

K=256 N=256
======= siftdown ======
No overlap: 0 lt; 68,385 gt; 0 eq
Interleaved: 0 lt; 917,880 gt; 0 eq
randomized42: 0 lt; 804,984 gt; 0 eq
randomized93: 0 lt; 804,315 gt; 0 eq
randomized11111: 0 lt; 803,782 gt; 0 eq

======= heapq.merge ======
No overlap: 737,140 lt; 0 gt; 737,140 eq
Interleaved: 524,478 lt; 0 gt; 524,478 eq
randomized42: 623,816 lt; 0 gt; 623,816 eq
randomized93: 623,034 lt; 0 gt; 623,034 eq
randomized11111: 624,139 lt; 0 gt; 624,139 eq

==== multimerge.merge ====
No overlap: 262,144 lt; 0 gt; 0 eq
Interleaved: 523,264 lt; 0 gt; 0 eq
randomized42: 523,064 lt; 0 gt; 0 eq
randomized93: 522,663 lt; 0 gt; 0 eq
randomized11111: 521,980 lt; 0 gt; 0 eq

K=256 N=512
======= siftdown ======
No overlap: 0 lt; 133,665 gt; 0 eq
Interleaved: 0 lt; 1,836,277 gt; 0 eq
randomized42: 0 lt; 1,627,786 gt; 0 eq
randomized93: 0 lt; 1,619,584 gt; 0 eq
randomized11111: 0 lt; 1,620,139 gt; 0 eq

======= heapq.merge ======
No overlap: 1,474,932 lt; 0 gt; 1,474,932 eq
Interleaved: 1,048,778 lt; 0 gt; 1,048,778 eq
randomized42: 1,238,296 lt; 0 gt; 1,238,296 eq
randomized93: 1,245,051 lt; 0 gt; 1,245,051 eq
randomized11111: 1,243,189 lt; 0 gt; 1,243,189 eq

==== multimerge.merge ====
No overlap: 524,288 lt; 0 gt; 0 eq
Interleaved: 1,047,552 lt; 0 gt; 0 eq
randomized42: 1,047,350 lt; 0 gt; 0 eq
randomized93: 1,047,344 lt; 0 gt; 0 eq
randomized11111: 1,046,616 lt; 0 gt; 0 eq

K=512 N=1
======= siftdown ======
No overlap: 0 lt; 7,203 gt; 0 eq
Interleaved: 0 lt; 7,203 gt; 0 eq
randomized42: 0 lt; 6,827 gt; 0 eq
randomized93: 0 lt; 6,872 gt; 0 eq
randomized11111: 0 lt; 6,619 gt; 0 eq

======= heapq.merge ======
No overlap: 5,014 lt; 0 gt; 5,014 eq
Interleaved: 5,014 lt; 0 gt; 5,014 eq
randomized42: 4,485 lt; 0 gt; 4,485 eq
randomized93: 4,477 lt; 0 gt; 4,477 eq
randomized11111: 4,449 lt; 0 gt; 4,449 eq

==== multimerge.merge ====
No overlap: 2,304 lt; 0 gt; 0 eq
Interleaved: 2,304 lt; 0 gt; 0 eq
randomized42: 3,887 lt; 0 gt; 0 eq
randomized93: 3,942 lt; 0 gt; 0 eq
randomized11111: 3,877 lt; 0 gt; 0 eq

K=512 N=2
======= siftdown ======
No overlap: 0 lt; 8,224 gt; 0 eq
Interleaved: 0 lt; 15,382 gt; 0 eq
randomized42: 0 lt; 13,909 gt; 0 eq
randomized93: 0 lt; 13,878 gt; 0 eq
randomized11111: 0 lt; 13,922 gt; 0 eq

======= heapq.merge ======
No overlap: 11,786 lt; 0 gt; 11,786 eq
Interleaved: 9,613 lt; 0 gt; 9,613 eq
randomized42: 9,365 lt; 0 gt; 9,365 eq
randomized93: 9,361 lt; 0 gt; 9,361 eq
randomized11111: 9,502 lt; 0 gt; 9,502 eq

==== multimerge.merge ====
No overlap: 4,608 lt; 0 gt; 0 eq
Interleaved: 6,912 lt; 0 gt; 0 eq
randomized42: 8,318 lt; 0 gt; 0 eq
randomized93: 8,307 lt; 0 gt; 0 eq
randomized11111: 8,428 lt; 0 gt; 0 eq

K=512 N=4
======= siftdown ======
No overlap: 0 lt; 9,246 gt; 0 eq
Interleaved: 0 lt; 31,774 gt; 0 eq
randomized42: 0 lt; 28,546 gt; 0 eq
randomized93: 0 lt; 28,380 gt; 0 eq
randomized11111: 0 lt; 28,205 gt; 0 eq

======= heapq.merge ======
No overlap: 25,330 lt; 0 gt; 25,330 eq
Interleaved: 18,805 lt; 0 gt; 18,805 eq
randomized42: 19,551 lt; 0 gt; 19,551 eq
randomized93: 19,777 lt; 0 gt; 19,777 eq
randomized11111: 19,597 lt; 0 gt; 19,597 eq

==== multimerge.merge ====
No overlap: 9,216 lt; 0 gt; 0 eq
Interleaved: 16,128 lt; 0 gt; 0 eq
randomized42: 17,132 lt; 0 gt; 0 eq
randomized93: 17,278 lt; 0 gt; 0 eq
randomized11111: 17,268 lt; 0 gt; 0 eq

K=512 N=8
======= siftdown ======
No overlap: 0 lt; 11,290 gt; 0 eq
Interleaved: 0 lt; 64,595 gt; 0 eq
randomized42: 0 lt; 57,632 gt; 0 eq
randomized93: 0 lt; 57,377 gt; 0 eq
randomized11111: 0 lt; 57,327 gt; 0 eq

======= heapq.merge ======
No overlap: 52,418 lt; 0 gt; 52,418 eq
Interleaved: 37,288 lt; 0 gt; 37,288 eq
randomized42: 40,800 lt; 0 gt; 40,800 eq
randomized93: 40,738 lt; 0 gt; 40,738 eq
randomized11111: 40,663 lt; 0 gt; 40,663 eq

==== multimerge.merge ====
No overlap: 18,432 lt; 0 gt; 0 eq
Interleaved: 34,560 lt; 0 gt; 0 eq
randomized42: 35,357 lt; 0 gt; 0 eq
randomized93: 35,367 lt; 0 gt; 0 eq
randomized11111: 35,341 lt; 0 gt; 0 eq

K=512 N=16
======= siftdown ======
No overlap: 0 lt; 15,378 gt; 0 eq
Interleaved: 0 lt; 130,121 gt; 0 eq
randomized42: 0 lt; 115,748 gt; 0 eq
randomized93: 0 lt; 115,593 gt; 0 eq
randomized11111: 0 lt; 116,241 gt; 0 eq

======= heapq.merge ======
No overlap: 106,594 lt; 0 gt; 106,594 eq
Interleaved: 74,172 lt; 0 gt; 74,172 eq
randomized42: 83,282 lt; 0 gt; 83,282 eq
randomized93: 83,179 lt; 0 gt; 83,179 eq
randomized11111: 83,098 lt; 0 gt; 83,098 eq

==== multimerge.merge ====
No overlap: 36,864 lt; 0 gt; 0 eq
Interleaved: 71,424 lt; 0 gt; 0 eq
randomized42: 71,930 lt; 0 gt; 0 eq
randomized93: 71,978 lt; 0 gt; 0 eq
randomized11111: 71,921 lt; 0 gt; 0 eq

K=512 N=32
======= siftdown ======
No overlap: 0 lt; 23,554 gt; 0 eq
Interleaved: 0 lt; 261,278 gt; 0 eq
randomized42: 0 lt; 231,634 gt; 0 eq
randomized93: 0 lt; 233,106 gt; 0 eq
randomized11111: 0 lt; 233,636 gt; 0 eq

======= heapq.merge ======
No overlap: 214,946 lt; 0 gt; 214,946 eq
Interleaved: 147,899 lt; 0 gt; 147,899 eq
randomized42: 169,017 lt; 0 gt; 169,017 eq
randomized93: 169,216 lt; 0 gt; 169,216 eq
randomized11111: 169,131 lt; 0 gt; 169,131 eq

==== multimerge.merge ====
No overlap: 73,728 lt; 0 gt; 0 eq
Interleaved: 145,152 lt; 0 gt; 0 eq
randomized42: 144,844 lt; 0 gt; 0 eq
randomized93: 145,401 lt; 0 gt; 0 eq
randomized11111: 145,644 lt; 0 gt; 0 eq

K=512 N=64
======= siftdown ======
No overlap: 0 lt; 39,906 gt; 0 eq
Interleaved: 0 lt; 523,327 gt; 0 eq
randomized42: 0 lt; 463,781 gt; 0 eq
randomized93: 0 lt; 463,390 gt; 0 eq
randomized11111: 0 lt; 464,198 gt; 0 eq

======= heapq.merge ======
No overlap: 431,650 lt; 0 gt; 431,650 eq
Interleaved: 295,378 lt; 0 gt; 295,378 eq
randomized42: 342,952 lt; 0 gt; 342,952 eq
randomized93: 342,811 lt; 0 gt; 342,811 eq
randomized11111: 343,112 lt; 0 gt; 343,112 eq

==== multimerge.merge ====
No overlap: 147,456 lt; 0 gt; 0 eq
Interleaved: 292,608 lt; 0 gt; 0 eq
randomized42: 292,498 lt; 0 gt; 0 eq
randomized93: 292,401 lt; 0 gt; 0 eq
randomized11111: 292,238 lt; 0 gt; 0 eq

K=512 N=128
======= siftdown ======
No overlap: 0 lt; 72,610 gt; 0 eq
Interleaved: 0 lt; 1,048,020 gt; 0 eq
randomized42: 0 lt; 930,303 gt; 0 eq
randomized93: 0 lt; 938,318 gt; 0 eq
randomized11111: 0 lt; 928,030 gt; 0 eq

======= heapq.merge ======
No overlap: 865,058 lt; 0 gt; 865,058 eq
Interleaved: 590,221 lt; 0 gt; 590,221 eq
randomized42: 689,797 lt; 0 gt; 689,797 eq
randomized93: 683,686 lt; 0 gt; 683,686 eq
randomized11111: 689,909 lt; 0 gt; 689,909 eq

==== multimerge.merge ====
No overlap: 294,912 lt; 0 gt; 0 eq
Interleaved: 587,520 lt; 0 gt; 0 eq
randomized42: 587,058 lt; 0 gt; 0 eq
randomized93: 586,878 lt; 0 gt; 0 eq
randomized11111: 586,835 lt; 0 gt; 0 eq

K=512 N=256
======= siftdown ======
No overlap: 0 lt; 138,018 gt; 0 eq
Interleaved: 0 lt; 2,097,027 gt; 0 eq
randomized42: 0 lt; 1,866,884 gt; 0 eq
randomized93: 0 lt; 1,870,596 gt; 0 eq
randomized11111: 0 lt; 1,861,719 gt; 0 eq

======= heapq.merge ======
No overlap: 1,731,874 lt; 0 gt; 1,731,874 eq
Interleaved: 1,180,029 lt; 0 gt; 1,180,029 eq
randomized42: 1,380,357 lt; 0 gt; 1,380,357 eq
randomized93: 1,379,021 lt; 0 gt; 1,379,021 eq
randomized11111: 1,382,798 lt; 0 gt; 1,382,798 eq

==== multimerge.merge ====
No overlap: 589,824 lt; 0 gt; 0 eq
Interleaved: 1,177,344 lt; 0 gt; 0 eq
randomized42: 1,176,217 lt; 0 gt; 0 eq
randomized93: 1,177,250 lt; 0 gt; 0 eq
randomized11111: 1,175,931 lt; 0 gt; 0 eq

K=512 N=512
======= siftdown ======
No overlap: 0 lt; 268,834 gt; 0 eq
Interleaved: 0 lt; 4,195,074 gt; 0 eq
randomized42: 0 lt; 3,763,285 gt; 0 eq
randomized93: 0 lt; 3,719,375 gt; 0 eq
randomized11111: 0 lt; 3,772,002 gt; 0 eq

======= heapq.merge ======
No overlap: 3,465,506 lt; 0 gt; 3,465,506 eq
Interleaved: 2,359,684 lt; 0 gt; 2,359,684 eq
randomized42: 2,749,886 lt; 0 gt; 2,749,886 eq
randomized93: 2,777,840 lt; 0 gt; 2,777,840 eq
randomized11111: 2,741,951 lt; 0 gt; 2,741,951 eq

==== multimerge.merge ====
No overlap: 1,179,648 lt; 0 gt; 0 eq
Interleaved: 2,356,992 lt; 0 gt; 0 eq
randomized42: 2,356,333 lt; 0 gt; 0 eq
randomized93: 2,356,164 lt; 0 gt; 0 eq
randomized11111: 2,356,351 lt; 0 gt; 0 eq

Stability is implied by the contract of

Calling < and == can be avoided by compare function, which return -1, 0, 1 So it's not real big deal in general maybe in python it is

Do I understand correctly difference of results with tournament tree of winners for overlapped and not cases because we cannot/don't need to compare with empty iterator?

If you don't need stability, another thing to try would be the "tournament tree of losers", where instead of storing the winner of each comparison, you store the loser, and that way each next(...) call moves from the leaf strictly up the tree.

Thanks! I will try it

[MBkkt]

Hmm, do I understand correctly count of comparison not changes for loser tree? It just avoid unnecessary lookup