This pull request would:

• Change heapq.merge to be a class whose instances are iterable objects, rather than a generator function.
• Change the algorithm for heapq.merge:
  • Before this PR, we repeatedly applied heapreplace on (index, iterator, item) tuples
    • Starting at the root, this would repeatedly replace parents with their smaller child. Upon reaching a leaf, it would replace that leaf using the __next__ method of the iterator corresponding to the the item we are replacing. It would then sift that new leaf down into the appropriate part of the heap.
  • After this PR, we would apply a "tree sift" method:
    • General algorithm: the items compete in a tournament, as we maintain a binary "tree of losers" (see Knuth Volume 3, Chapter 5.4.1. on "Multiway Merging").
    • Here, we only need to store individual items, or key-item pairs.
    • After popping off the root, we replace it with its smaller child, the child with its smaller child, etc., until reaching a leaf. So far, this is identical to the standard siftup method.
    • However, once reaching a leaf, we replace the leaf with the iterator corresponding to the index of that leaf. That is, always filling the leftmost leaf with the first iterable that was passed, the second-leftmost with the second-passed, ..., and the rightmost leaf with the last iterable passed.
    • This eliminates the need to sift the leaf down afterward because we already know that it is larger than the item it replaces.
    • For tree sizes that aren't a power of two, permuting the iterators so that the first one is leftmost is simply a matter of shifting all iterators around the list by a few spots.
    • Heuristically, removing the requirement that there be exactly one item from each iterator in the heap at a time makes the heap more likely to consist of those items which are closest.
    • Storing the tree flatly (for the C implementation, even when using a key), rather than having a tuple at each node helps with cache locality.
    • This is a non-recursive version of recursively applying a function that merges two iterables.
• Add the corresponding C and Python implementations.
• Add a test case for error handling in heapq.merge

According to my benchmarking, this is at least 2.5 times as fast in almost all cases to the existing implementation, and is especially fast (about 5x as fast as the existing way) with small numbers of iterables. I tested up to 12,000 iterables, with varying degrees of "balance" among the number of items in each. Also noteworthy is that fewer comparisons on average were needed with the proposed new method.

https://bugs.python.org/issue38938