Python heapq vs sorted speed for pre-sorted lists
<p>I have a reasonably large number n=10000 of sorted lists of length k=100 each. Since merging two sorted lists takes linear time, I would imagine its cheaper to recursively merge the sorted lists of length O(nk) with <code>heapq.merge()</code> in a tree of depth log(n) than to sort the entire thing at once with <code>sorted()</code> in O(nklog(nk)) time.</p>

<p>However, the <code>sorted()</code> approach seems to be 17-44x faster on my machine. Is the implementation of <code>sorted()</code> that much faster than <code>heapq.merge()</code> that it outstrips the asymptotic time advantage of the classic merge?</p>

<pre><code>import itertools
import heapq

data = [range(n*8000,n*8000+10000,100) for n in range(10000)]

# Approach 1
for val in heapq.merge(*data):
    test = val

# Approach 2
for val in sorted(itertools.chain(*data)):
    test = val
</code></pre>