Internal working of python heapq merge. How does it sort a list without generating the list

Question

How does heapq.merge() sort a list even without generate the list?

Not sure if I stated clear.
So, this is raised from the Super Ugly Number problem at leetcode.

And this python code

class Solution(object):
    def nthSuperUglyNumber(self, n, primes):
        """
        :type n: int
        :type primes: List[int]
        :rtype: int
        """
        uglies = [1]
        def gen(prime):
            for ugly in uglies:
                yield ugly * prime
        merged = heapq.merge(*map(gen, primes))
        while len(uglies) < n:
            ugly = next(merged)
            if ugly != uglies[-1]:
                uglies.append(ugly)
        return uglies[-1]

gave me a hard time understanding it. After I searched the concepts of "yield" and "heapq", I still don't get that in the while loop, how merged know that ugly in uglies>n will not be smaller than uglies[n-1].

Answer 1

The implementation of heapq.merge is pure Python, you can read its code directly if you want.

As you might guess from the module it's implemented in, it uses a heap to merge the iterables it's passed. If the iterables (generators in this case) each yield their values in order, it will combine them so that the values it yields are also in order. It doesn't eliminate duplicate values, which is why the code you show checks to see if the latest value is equal to the previous one.