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

Mike C. Fletcher mcfletch at rogers.com
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
>fixed.
>
>
Sorry about that, revised version below:

def firstIter( value ):
it = iter( value )
try:
return it.next(), 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 = [
[value,it]
for (value,it) in [ firstIter( arg ) for arg in args ]
if it is not None
]
iterators.sort()
while iterators:
yield iterators[0][0]
try:
value = iterators[0][0] = iterators[0][1].next()
except StopIteration, err:
iterators.pop(0)
else:
if len(iterators) > 1 and comparison( value,
iterators[1][0]) == 1:
iterators.sort( cmpFirstWith( comparison ) )
continue

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

--
________________________________________________
Mike C. Fletcher
Designer, VR Plumber, Coder
http://www.vrplumber.com
http://blog.vrplumber.com

```