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)