Merging sorted lists/iterators/generators into one stream of values...

Mike C. Fletcher mcfletch at
Fri Oct 7 18:53:42 CEST 2005

Lasse Vågsæther Karlsen wrote:

>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 ?
Correct, comparison is recursive for lists/tuples.

>2. sort(), pop() is not costly operations
They *can* be costly, but the algorithm reduces the number of times they 
are called to less-than-linear for all but pathological cases (i.e. they 
are only called when you need to switch streams).  It also only requires 
sorting only the number of streams, rather than the whole set.

>Other than that you seem to not use the cmp operator but that's easily
Sorry about that, revised version below:

def firstIter( value ):
    it = iter( value )
        return, it
    except StopIteration, err:
        return None, None

def cmpFirstWith( comparison ):
    def compare( a,b ):
        return comparison(a[0],b[0])
    return compare

def inorder( comparison, *args ):
    iterators = [
        for (value,it) in [ firstIter( arg ) for arg in args ]
        if it is not None
    while iterators:
        yield iterators[0][0]
            value = iterators[0][0] = iterators[0][1].next()
        except StopIteration, err:
            if len(iterators) > 1 and comparison( value, 
iterators[1][0]) == 1:
                iterators.sort( cmpFirstWith( comparison ) )

if __name__ == "__main__":
    s1 = [10, 20, 30, 40, 50]
    s2 = [15, 25]
    s3 = [17, 27, 37]
    s4 = []
    for value in inorder(cmp, s1, s2, s3, s4):
        print value
    s1 = [{'a':'b'}, {'a':'e'}]
    s2 = [{'a':'d'}, {'a':'z'}]
    def comp( a,b ):
        return cmp( a['a'],b['a'])
    for value in inorder(cmp, s1, s2 ):
        print value

Have fun,

  Mike C. Fletcher
  Designer, VR Plumber, Coder

More information about the Python-list mailing list