from collections import Counter

import hypothesis.strategies as st
import hypothesis as hp
import pytest

def merge(xs, ys):                      
    xs, ys = iter(xs), iter(ys)
    none = object()
    y = next(ys, none)
    if y is not none:
        while True:
            try:
                x = next(xs)
                if x > y:
                    x, xs, y, ys = y, ys, x, xs
                yield x
            except StopIteration:
                yield y
                break
    else:
        ys = xs
    yield from ys


@hp.given(st.lists(st.integers()), st.lists(st.integers()))
def test_merge(xs, ys):
    merged = list(merge(sorted(xs), sorted(ys)))
    assert all(x <= y for x, y in zip(merged, merged[1:]))
    assert Counter(xs + ys) == Counter(merged)