def merge(iterables, key=None, reverse=False):
    '''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]
    If *key* is not None, applies a key function to each element to determine
    its sort order.
    >>> list(merge(['dog', 'horse'], ['cat', 'fish', 'kangaroo'], key=len))
    ['dog', 'cat', 'fish', 'horse', 'kangaroo']
    '''
    h = []
    h_append = h.append
    if reverse:
        _heapify = _heapify_max
        _heappop = _heappop_max
        _heapreplace = _heapreplace_max
        direction = -1
    else:
        _heapify = heapify
        _heappop = heappop
        _heapreplace = heapreplace
        direction = 1
    if key is None:
        for order, it in enumerate(map(iter, iterables)):
            try:
                h_append([next(it), order * direction, it])
            except StopIteration:
                pass
        _heapify(h)
        while len(h) > 1:
            try:
                while True:
                    value, order, it = s = h[0]
                    yield value
                    s[0] = next(it)
                    _heapreplace(h, s)
            except StopIteration:
                _heappop(h)
        if h:
            value, order, it = h[0]
            yield value
            for value in it:
                yield value
        return
    for order, it in enumerate(map(iter, iterables)):
        try:
            value = next(it)
            h_append([key(value), order * direction, value, it])
        except StopIteration:
            pass
    _heapify(h)
    while len(h) > 1:
        try:
            while True:
                key_value, order, value, it = s = h[0]
                yield value
                value = next(it)
                s[0] = key(value)
                s[2] = value
                _heapreplace(h, s)
        except StopIteration:
            _heappop(h)
    if h:
        key_value, order, value, it = h[0]
        yield value
        for value in it:
            yield value