Product of dictionary values
You can use the fact that d.keys() and d.values() are always aligned. This gets rid of both the awkward way of constructing the values as well as the sorting of the keys.

def dict_product(d):
    keys = d.keys()
    for element in product(*d.values()):
        yield dict(zip(keys, element))


The assignment of keys is not strictly necessary, but it avoids the look-up every loop iteration.



Note that list(d[k] for k in sorted_keys) should have been written as a list comprehension directly, instead of calling list on a generator comprehension. So [d[k] for k in sorted_keys].



Your doctest might fail in Python 2 or in Python implementations other than cPython. This is because only recently have dictionary keys become ordered (by insertion time) in (c)Python 3. This is still an implementation detail and not something you should rely upon. Since doctest performs a string comparison, it does not notice that the objects are actually the same.

The only way around this, at least the only one I can see, is to use a more sophisticated testing framework, like unittest. This comes with more code overhead, though.