O(nlogk) algorithm for k-way merge

gistfile1.txt

def merge2(arr):
    heap = [(l[0],i,0) for i,l in enumerate(arr) if len(l) > 0]
    heapq.heapify(heap)
    lst = []
    while heap:
        item,lst_index,item_index = heapq.heappop(heap)
        lst.append(item)
        if item_index + 1 < len(arr[lst_index]):
            heapq.heappush(heap,(arr[lst_index][item_index+1],lst_index,item_index+1))
    return lst