K-way-merge without heapq and any other libraries using python

Question

Can anyone tell me what's wrong with my code? Input is n iterators. I need to make generator which yields values of merged list on fly. I don't want use heapq, queue or deque.

    #!/usr/bin/python

    def min_(ar):
        l = list()
        for val, array in ar:
            l.append(val)
        return l.index(min(l))

    def k_way_merge(*args):
        data = list()
        for array in args:
            data.append((array.next(), array))

        while data:
            index = min_(data)
            key, value = data[index]
            data.remove(data[index])
            yield key
            if value:
                data.append((next(value), value))



    l=[[1,3], [2,4], [10,100],[100,101]]
    res = k_way_merge(iter(l[0]), iter(l[1]),iter(l[2]),iter(l[3]))
    for i in res:
        print i

result is:

1  
2
3

It seems that next(value) raises StopIteration, but how to repair all that...Help

Answer 1

iterators don't evaluate to False when they are empty. You have to use the next builtin with a sentinel value:

END = object()
while data:
    index = min_(data)
    key, value = data.pop(index)
    yield key
    key = next(value, END)
    if key is not END:
        data.append((key, value))

Also, since min_ returns the index, why use data.remove(data[index]) - just use pop.

Answer 2

You need to make this operation optional if value is empty:

        if value:
            data.append((next(value), value))

This change works for me:

if value:
    try:
        data.append(next(value), value)
    except StopIteration:
        pass