title: heapq.merge() iterator goes through more items than in the lists
body: <p>Following the <a href="https://docs.python.org/2/library/heapq.html" rel="nofollow noreferrer">docs</a> of heapq.merge() - I get very strange results, and cannot find what am I doing wrong... The setup is as follows:</p>
  
  <ol>
  <li>I am using heapq.merge() to sort multiple lists. Tested with 2 ~ 8 list iterators, and the results are exactly the same. The lists contain 10K ~ 25K items.</li>
  <li>The lists elements themselves implement all that is required for the lists to be sorted (__ lt__(), __ eq__(), ...). </li>
  <li>I tested that these special sorting methods are called, both when sorting the lists themselves, and while the heapq.merge() method is called.</li>
  <li>I made sure that the lists do not contain any duplicate entry. Not even cross list. Using a simple running number which I appended to each element, and which is used in the comparison.</li>
  </ol>
  
  <p>The output:
  While iterating through 2 lists with 25K items each, I got 100K results. <strong>Double the amount put in.</strong></p>
  
  <p>I believe I followed all the requirements here. Should I heapify the lists before entering them into the heapq.merge? It is not said so in the <a href="https://docs.python.org/2/library/heapq.html" rel="nofollow noreferrer">docs</a> and it is not clear how should/if it be done.</p>
  
  <p>Any clue?</p>