import timeit
import random
from heapq import *

# copied from ca2a35140e6a
def merge_baseline(*iterables):
    '''Merge multiple sorted inputs into a single sorted output.

    Similar to sorted(itertools.chain(*iterables)) but returns a generator,
    does not pull the data into memory all at once, and assumes that each of
    the input streams is already sorted (smallest to largest).

    >>> list(merge([1,3,5,7], [0,2,4,8], [5,10,15,20], [], [25]))
    [0, 1, 2, 3, 4, 5, 5, 7, 8, 10, 15, 20, 25]

    '''
    _heappop, _heapreplace, _StopIteration = heappop, heapreplace, StopIteration

    h = []
    h_append = h.append
    for itnum, it in enumerate(map(iter, iterables)):
        try:
            next = it.__next__
            h_append([next(), itnum, next])
        except _StopIteration:
            pass
    heapify(h)

    while 1:
        try:
            while 1:
                v, itnum, next = s = h[0]   # raises IndexError when h is empty
                yield v
                s[0] = next()               # raises StopIteration when exhausted
                _heapreplace(h, s)          # restore heap condition
        except _StopIteration:
            _heappop(h)                     # remove empty iterator
        except IndexError:
            return


def merge_1(*iterables, key=None):
    _heappop, _heapreplace, _StopIteration = heappop, heapreplace, StopIteration

    if key is None:
        key = lambda x: x
    h = []
    h_append = h.append
    for itnum, it in enumerate(map(iter, iterables)):
        try:
            next = it.__next__
            v = next()
            h_append([key(v), itnum, v, next])
        except _StopIteration:
            pass
    heapify(h)

    while 1:
        try:
            while 1:
                k, itnum, v, next = s = h[0] # raises IndexError when h is empty
                yield v
                v = next()                  # raises StopIteration when exhausted
                s[0] = key(v)
                s[2] = v
                _heapreplace(h, s)          # restore heap condition
        except _StopIteration:
            _heappop(h)                     # remove empty iterator
        except IndexError:
            return


def merge_2(*iterables, key=None):
    _heappop, _heapreplace, _StopIteration = heappop, heapreplace, StopIteration

    h = []
    h_append = h.append
    key_is_None = key is None
    for itnum, it in enumerate(map(iter, iterables)):
        try:
            next = it.__next__
            v = next()
            h_append([v if key_is_None else key(v), itnum, v, next])
        except _StopIteration:
            pass
    heapify(h)

    while 1:
        try:
            while 1:
                k, itnum, v, next = s = h[0] # raises IndexError when h is empty
                yield v
                v = next()                  # raises StopIteration when exhausted
                s[0] = v if key_is_None else key(v)
                s[2] = v
                _heapreplace(h, s)          # restore heap condition
        except _StopIteration:
            _heappop(h)                     # remove empty iterator
        except IndexError:
            return


def merge_3(*iterables, key=None):
    _heappop, _heapreplace, _StopIteration = heappop, heapreplace, StopIteration

    h = []
    h_append = h.append
    if key is None:
        for itnum, it in enumerate(map(iter, iterables)):
            try:
                next = it.__next__
                v = next()
                h_append([v, itnum, next])
            except _StopIteration:
                pass
    else:
        for itnum, it in enumerate(map(iter, iterables)):
            try:
                next = it.__next__
                v = next()
                h_append([key(v), itnum, v, next])
            except _StopIteration:
                pass
    heapify(h)

    if key is None:
        while 1:
            try:
                while 1:
                    # raises IndexError when h is empty
                    v, itnum, next = s = h[0]
                    yield v
                    v = next()          # raises StopIteration when exhausted
                    s[0] = v
                    _heapreplace(h, s)  # restore heap condition
            except _StopIteration:
                _heappop(h)             # remove empty iterator
            except IndexError:
                return
    else:
        while 1:
            try:
                while 1:
                    # raises IndexError when h is empty
                    k, itnum, v, next = s = h[0]
                    yield v
                    v = next()          # raises StopIteration when exhausted
                    s[0] = key(v)
                    s[2] = v
                    _heapreplace(h, s)  # restore heap condition
            except _StopIteration:
                _heappop(h)             # remove empty iterator
            except IndexError:
                return


# Fixed seed to get consistent runs
random.seed(17)
inputs = [
    sorted(random.randrange(1000) for j in range(random.randrange(100)))
    for i in range(random.randrange(50))
]
repeat = 3
number = 30
baseline = None
for function in [merge_baseline, merge_1, merge_2, merge_3]:
    def test():
        list(function(*inputs))
    timer = timeit.Timer(test)
    runs = timer.repeat(repeat, number)
    result = min(runs) * 1000 / number
    print(function.__name__)
    print('per run, min of', repeat, '=', round(result, 3), 'ms')
    if baseline is None:
        baseline = result
    else:
        print(round(100 * result / baseline, 3), '% of baseline')
    print()