This method saves "<" comparisons in almost all cases, especially when one iterable wins repeatedly. It also eliminates the "==" comparisons required in the tuple comparisons of the previous algorithm. Sort stability is maintained by the structure of the tree rather than by storing indices.
This follows https://bugs.python.org/issue38938 (thanks Raymond Hettinger for the basic implementation idea)
PyPy Benchmarks:
pypy -m pyperf timeit -s "from random import random; from heapq import merge; from collections import deque; iters = [sorted(random() for j in range(10_000)) for i in range(20)]" "deque(merge(*iters), maxlen=0)"
Mean +- std dev: 142 ms +- 1 ms
pypy -m pyperf timeit -s "from random import random; from NEW_HEAPQ import merge; from collections import deque; iters = [sorted(random() for j in range(10_000)) for i in range(20)]" "deque(merge(*iters), maxlen=0)"
Mean +- std dev: 38.8 ms +- 0.6 ms
--HG-- branch : heapq_merge