It can be done on O(nk log k) if you always merge two shortest list. If all the lists have length k initially it can be easily done with couple of loops as all the lists will have the same length - n in the beginning, 2n after fist iteration, 4n after second.