Although the implementation of the heapq.merge function uses an underlying heap structure, its behavior centers on iterators. For this reason, I believe there should either be an alias to this function in the itertools module or at least a recipe in the itertools docs describing the use of heapq.merge.

Furthermore, I have an implementation (attached) of heapq.merge that is twice as fast for two iterables (as used in mergesort and other common cases), and is faster for up to 6 or 7 iterables. I think it would be nice to special-case this for small numbers of iterables for this significant speedup.

The following seems like it is a short, readable recipe for itertools.

Disregard merge_recipe.py: it would skip over a value that had already been retrieved from the iterator when the loop finished.

Several thoughts:

* heapq.merge() could have plausibly been in the itertools module instead of the heapq module.  However, since it already has a home, there is no reason to move it or to create duplication with an intermodule dependency.  We certainly don't have a rule that the itertools module must house everything accepts an iterator as an input and returns an iterator in the output.

* The iter_merge() recipe is a bit sprawling and IMHO not a useful teaching aid (a primary goal of the itertools recipe), so it doesn't have much documentation value.  Instead, consider submitting this to the "more-itertools" project which is referenced by the docs.  There it would likely be used directly rather than as a recipe.

* Over the next few days, I'll take a closer look at the binary tree approach versus a heap approach.  I like how it intrinsically avoids the overhead of the 4-tuple while maintaining order, but I want to test how well it does with slow comparison keys (i.e. does the total number of comparisons get worse).  Am not sure whether the tree needs to be rebalanced as some of the input streams become exhausted.  I have a vague recollection that Knuth's TAOCP deemed the heap approach to be algorithmically superior, but need to dig out my books to be verify that.

* We could just build-out the current heapq.merge() code to include a special case for only two input iterables.  That would speed-up a common case by avoiding the overhead of tracking a 4-tuple for each element.  If you want to submit a PR for that, I would be happy to take a close look and verify the timings.

* It might be interesting to time the pure python variants against "sorted(chain(a, b, c, d, e))".  It isn't quite an apples-to-apples comparison because the latter pulls all the data in memory and it doesn't the runs pre-segregated, but it might give a sense of how well merge() could do if we decided to go gonzo on optimizations.  Until now, we've been satisfied with letting the heap structure minimize the number of comparisons and there hasn't been a focus on reducing the constant factor overhead.

PR 17729 is a C implementation of a non-recursive "flattening" of the the recursive-lazy-mergesort algorithm into a tournament whose state is a tree of losers of comparisons.