ActiveState Code

Recipe 440551: Merging sorted iterables

Whoops... please delete it, it's a duplicate... There's an almost identical implementation in chapter 19.14 of the Python Cookbook. I'm not anymore sure if I wrote this from scratch a while ago.

Suppose you have some sorted iterables, and you want to get them merged preserving ordering, without consuming iterables (and computing time) unnecessarily. This recipe may come in handy.

Python 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import heapq

def imerge(iterables):
    """Merge sorted iterables."""

    iterables = [iter(x) for x in iterables]
    queue = []
    for i, it in enumerate(iterables):
        try:
            heapq.heappush(queue, (it.next(), i))
        except StopIteration:
            pass
    while queue:
        item, topit = queue[0]
        yield item
        try:
            heapq.heapreplace(queue, (iterables[topit].next(), topit))
        except StopIteration:
            heapq.heappop(queue)

>>> it1 = [34, 76, 77, 99]
>>> it2 = [0, 3, 56, 70]
>>> it3 = [2, 7, 9, 14]
>>> list(imerge([it1, it2, it3]))
[0, 2, 3, 7, 9, 14, 34, 56, 70, 76, 77, 99]

Discussion

If you want to consume all data, or if data samples are short, you could also just do something along the lines of

>>> sorted(itertools.chain(it1, it2, it3))

Anyway, iterables can be very large - possibly infinite - and you may want to save your computer the hassle of producing and sorting data that may not be used. Using this recipe, you are sure you'll just work on the ones you need.

Sign in to comment