title: Internal working of python heapq merge. How does it sort a list without generating the list
body: <p>How does <code>heapq.merge()</code> sort a list even without generate the list?</p>
  <p>Not sure if I stated clear.<br />
  So, this is raised from the
  <a href="https://leetcode.com/problems/super-ugly-number/" rel="nofollow noreferrer">Super Ugly Number problem at leetcode</a>.</p>
  <p>And this python code</p>
  <pre class="lang-py prettyprint-override"><code>class Solution(object):
      def nthSuperUglyNumber(self, n, primes):
          &quot;&quot;&quot;
          :type n: int
          :type primes: List[int]
          :rtype: int
          &quot;&quot;&quot;
          uglies = [1]
          def gen(prime):
              for ugly in uglies:
                  yield ugly * prime
          merged = heapq.merge(*map(gen, primes))
          while len(uglies) &lt; n:
              ugly = next(merged)
              if ugly != uglies[-1]:
                  uglies.append(ugly)
          return uglies[-1]
  </code></pre>
  <p>gave me a hard time understanding it. After I searched the concepts of &quot;yield&quot; and &quot;heapq&quot;, I still don't get that in the <code>while</code> loop, how <code>merged</code> know that <code>ugly in uglies&gt;n</code> will not be smaller than <code>uglies[n-1]</code>.</p>