import heapq def imerge(*iterables): '''Merge multiple sorted inputs into a single sorted output. Equivalent to: sorted(itertools.chain(*iterables)) >>> list(imerge([1,3,5,7], [0,2,4,8], [5,10,15,20], [], [25])) [0, 1, 2, 3, 4, 5, 5, 7, 8, 10, 15, 20, 25] ''' heappop, siftup, _StopIteration = heapq.heappop, heapq._siftup, StopIteration h = [] h_append = h.append for it in map(iter, iterables): try: next = it.next h_append([next(), next]) except _StopIteration: pass heapq.heapify(h) while 1: try: while 1: v, next = s = h[0] # raises IndexError when h is empty yield v s[0] = next() # raises StopIteration when exhausted siftup(h, 0) # restore heap condition except _StopIteration: heappop(h) # remove empty iterator except IndexError: return if __name__ == '__main__': import doctest doctest.testmod()