def merge(*iterables, key=None, reverse=False):
n = len(iterables)
if not n:
return
n_1 = n - 1
# shift the iterators so that the first iterable passed will
# correspond to the leftmost node
shift = n - (1 << n.bit_length())
iters = [iter(iterables[i+shift]) for i in range(n)]
# tree will be a binary heap structure, but we won't do the usual
# heap operations. Items will only ever move toward the root, and
# the leaves will be supplied by the iterators. This a non-recursive
# implementation of recursively applying a 2-iterator merge.
# Each item will only appear in the tree once.
tree = [None] * (n+n_1)
sentinel = object()
_next = next
_StopIteration = StopIteration
for pos in reversed(range(len(tree))):
# "heapify", with new leaves coming from iterators rather than swaps
while pos < n_1:
childpos = 2 * pos + 1
child = tree[childpos]
otherchild = tree[childpos + 1]
if otherchild is not sentinel \
and (child is sentinel or otherchild < child):
childpos += 1
child = otherchild
tree[pos] = child
pos = childpos
tree[pos] = _next(iters[pos - n_1], sentinel)
while True:
result = tree[0]
if result is sentinel:
return
yield result
# "siftup", with new leaves coming iterators.
# i.e., replace each parent with its better child
pos = 0
while pos < n_1:
childpos = 2 * pos + 1
child = tree[childpos]
otherchild = tree[childpos + 1]
if otherchild is not sentinel \
and (child is sentinel or otherchild < child):
childpos += 1
child = otherchild
tree[pos] = child
pos = childpos
tree[pos] = _next(iters[pos - n_1], sentinel)