Merging multiple sorted sequences.

[Ian Kelly]

On Wed, Apr 12, 2017 at 4:15 PM, Erik <python at lucidity.plus.com> wrote:
> Hi.
>
> I need to be able to lazily merge a variable number of already-sorted(*)
> variable-length sequences into a single sorted sequence. The merge should
> continue until the longest sequence has been exhausted.
>
> (*) They may in practice be a lazy source of data known to only ever be
> generated in an order that's "sorted" from the POV of this function.
>
> I have the following - can anyone think of any improvements (other than
> indentation style on the try/excepts ;) )? This seems like the sort of thing
> for which there might be a built-in or recipe that I've missed.

There probably should be. I know I've implemented something similar in the past.

> -----------------------------------------
> def merge(*sources):
>     items = []
>     for source in (iter(s) for s in sources):
>        try: items.append([next(source), source])
>        except StopIteration: pass
>
>     while len(items) > 1:
>         items.sort(key=lambda item: item[0])

This might be okay since Timsort on an already-sorted list should be
O(n). But there's not really any need to keep them sorted and I would
just use "lowest = min(items, key=itemgetter(0))".

>         lowest = items[0]
>         yield lowest[0]
>
>         try: lowest[0] = next(lowest[1])
>         except StopIteration: del items[0]
>
>     if len(items) != 0:

"if items:"

>        yield items[0][0]
>        yield from items[0][1]
> -----------------------------------------