Merge Sorted Streams

Several servers each write a log sorted by time, and you want one timeline. The logs can be huge or still growing, so reading them all into memory and sorting is not an option.

Write a generator merge_sorted(*iterables, key=None) that takes any number of iterables, each already sorted, and yields all their items in sorted order.

• Items are compared by key(item), or by the items themselves when key is None.
• Ties keep a stable order: for finite inputs the result is exactly sorted(itertools.chain(*iterables), key=key). So items with equal keys come out in the order of the iterables they came from, and items from one iterable keep their order.
• It must be lazy: it starts by reading the first item of each iterable, and then reads one more item from an iterable only when it yields one of that iterable's items. So it works when some iterables never end.

You may use heapq, but not heapq.merge: building the merge is the point.

Examples

list(merge_sorted([1, 4, 9], [2, 3, 10], [5]))
# returns [1, 2, 3, 4, 5, 9, 10]

list(merge_sorted(['b', 'd'], ['a', 'c', 'e']))
# returns ['a', 'b', 'c', 'd', 'e']

web = [(1, 'web: start'), (5, 'web: ok')]
db = [(1, 'db: start'), (3, 'db: ok')]
list(merge_sorted(web, db, key=lambda e: e[0]))
# returns [(1, 'web: start'), (1, 'db: start'), (3, 'db: ok'), (5, 'web: ok')]

In the last example both logs have an entry at time 1, and the one from the first log comes first.

Constraints

• Up to 1,000 iterables and 200,000 items in total; some iterables may never end
• Items with equal keys might not be comparable with each other (two dicts, for example), so never compare the items themselves when a key is given