Thanks Raymond, that is exactly what I had in mind (see my previous comment).
Here's a slightly cleaned up version of the patch (stylistic/PEP8 cleanups),
with some benchmarks included below.

In case the two longest iterators have about the same size, no performance
difference can be measured:

$ ./python -m timeit -s 'from heapq import merge' 'for x in merge([], [], [1], range(100), range(100)): pass'

Without patch:

10000 loops, best of 3: 71.2 usec per loop
10000 loops, best of 3: 71.9 usec per loop
10000 loops, best of 3: 71.7 usec per loop

With patch:

10000 loops, best of 3: 71.4 usec per loop
10000 loops, best of 3: 76.7 usec per loop
10000 loops, best of 3: 72.1 usec per loop

As expected, the performance gain is very significant in case one of the
iterators is much longer than the others:

$ python -m timeit -n 100 -s 'from heapq import merge' 'for x in merge([], [], [1], range(100), range(100000)): pass'

Without path:

100 loops, best of 3: 27.8 msec per loop
100 loops, best of 3: 26.9 msec per loop
100 loops, best of 3: 27.7 msec per loop

With patch:

100 loops, best of 3: 6.26 msec per loop
100 loops, best of 3: 6.28 msec per loop
100 loops, best of 3: 6.03 msec per loop