merge sorted

gistfile1.py

def merge_sorted(*iterables, **kwargs):
    """Returns a generator that merges N sorted iterables.

    An optional `cmp` keyword argument may be supplied to customize the
    comparison between values produced by the iterables.
    """

    compare = kwargs.get('cmp', cmp)
    direction = -1 if kwargs.get('reverse', False) else 1

    iters = []
    current = []

    # Convert into iterables and fill the first set to compare
    for i in iterables:
        _iter = iter(i)

        try:
            current.append(next(_iter))
            iters.append(_iter)
        except StopIteration:
            pass

    last_index = None

    while True:
        if last_index is not None:
            try:
                current[last_index] = next(iters[last_index])
            except StopIteration:
                current.pop(last_index)
                iters[last_index] = None

        # Nothing more to process
        if not current:
            break

        # Remove consumed iterators
        iters = [i for i in iters if i is not None]

        # Start with the first element
        selected = current[0]
        last_index = 0

        for i, v in enumerate(current):
            # The selected value is less than the current one,
            # replace it
            if i != 0 and compare(selected, v) == direction:
                selected = v
                last_index = i

        yield selected