st0le
9/21/2013 - 2:35 AM

k-way merge

k-way merge

def merge(arr):
    k = len(arr)
    index = [0] * k
    lst = []
    while True:
        mni = None
        for i in xrange(k):
            if index[i] < len(arr[i]) and (mni == None or arr[i][index[i]] < arr[mni][index[mni]]):
                mni = i
        if mni == None: break
        lst.append(arr[mni][index[mni]])
        index[mni] += 1
    return lst