Ok, that one looks more sleak than what I came up with. Couple of things I learn from your solution, please correct me if I misunderstood something:
1. list containing other lists will sort itself based on first element on lists inside ? 2. sort(), pop() is not costly operations Other than that you seem to not use the cmp operator but that's easily fixed. This one looks much better than mine, here's what I came up with: def merge_sorted(iterables, comparer=None): """ Generator that will take a list of iterables/generators that is individually sorted, and then produce values in a sorted order by taking the lowest value from each source each call. @param iterables: List of iterables/generators to retrieve values from @type iterables: List of iterables/generators @param comparer: Optional fn(v1, v2) function that can compare two values, should return <0 if v1<v2, >0 if v1>v2 and ==0 if v1==v2. @type comparer: function-object, example: lambda x, y: x-y @note: The "list of iterables" can actually be anything that produces a list of iterables, so you can use a function that yields lists for instance. """ # First convert whatever we're given into a list of sources iterables = [iterable for iterable in iterables] # This series of if-statements will determine how many sources we have and work out sub-problems # that are manageable. if len(iterables) != 2: if len(iterables) == 0: # List, but no sources pass elif len(iterables) == 1: # Only 1 source, just return its contents for value in iterables[0]: yield value elif len(iterables) == 3: # 3 sources, sub-divide into 0 <--> (1, 2) left_iterable = iterables[0] right_iterable = merge_sorted([iterables[1], iterables[2]], comparer) for value in merge_sorted([left_iterable, right_iterable], comparer): yield value elif len(iterables) == 4: # 4 sources, sub-divide into (0, 1) <--> (2, 3) left_iterable = merge_sorted([iterables[0], iterables[1]], comparer) right_iterable = merge_sorted([iterables[2], iterables[3]], comparer) for value in merge_sorted((left_iterable, right_iterable), comparer): yield value elif len(iterables) > 4: # >4 sources, sub-divide into (0, 1) <--> (2, ...) left_iterable = merge_sorted([iterables[0], iterables[1]], comparer) right_iterable = merge_sorted(iterables[2:], comparer) for value in merge_sorted((left_iterable, right_iterable), comparer): yield value raise StopIteration # The method will only get here if there is only two sources, which is an easy case to handle i1 = iter(iterables[0]) i2 = iter(iterables[1]) # Grab the first two values from the two sources, if possible try: v1 = i1.next() has_v1 = True except StopIteration: has_v1 = False try: v2 = i2.next() has_v2 = True except StopIteration: has_v2 = False # As long as we got values from both generates/iterators/whatever, compare and yield the lowest of the # two, and then get the next value from the corresponding source while has_v1 and has_v2: # Work out which of v1 and v2 comes first if comparer is not None: comp = comparer(v1, v2) if comp <= 0: yield_v1 = True else: yield_v1 = False else: if v1 <= v2: yield_v1 = True else: yield_v1 = False # Yield the next value, then grab a new value from the corresponding source if yield_v1: yield v1 try: v1 = i1.next() except StopIteration: has_v1 = False else: yield v2 try: v2 = i2.next() except StopIteration: has_v2 = False # When we get here, we got 3 possibilities: # 1. has_v1 == True, has_v2 == False --> yield rest of v1/i1 and just exit on StopIteration exception # 2. has_v1 == False, has_v1 == True --> yield rest of v2/i2 and just exit on StopIteration exception # 3. has_v1 == has_v2 == False --> while-loops will skip, function falls off the end while has_v1: yield v1 v1 = i1.next() while has_v2: yield v2 v2 = i2.next() -- http://mail.python.org/mailman/listinfo/python-list