Optimize heapq.merge()

Closed Dennis Sweeney requested to merge branch/heapq_merge into branch/default

For performance, re-implement heapq.merge() using a linked tournamet tree.

This follows https://bugs.python.org/issue38938. Some benchmarks for PyPy:

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

Merge request reports