Interleaving two numpy index arrays, one item from each array

You could break the problem into two parts:

1. Make a and b iterators which yield values only if they are bigger than some threshold.
2. Use itertools (essentially George Sakkis' roundrobin recipe) to alternate between the two iterators.

import itertools
import numpy as np

a = np.array([1,2,3,4,7,8,9,10,17])
b = np.array([5,6,13,14,15,19,21,23])

def takelarger(iterable):
    for x in iterable:
        if x > takelarger.threshold:
            takelarger.threshold = x
            yield x
takelarger.threshold = 0

def alternate(*iterables):
    # Modified version of George Sakkis' roundrobin recipe
    # http://docs.python.org/library/itertools.html#recipes
    pending = len(iterables)
    nexts = itertools.cycle(iter(it).next for it in iterables)
    while pending:
        try:
            for n in nexts:
                yield n()
        except StopIteration:
            # Unlike roundrobin, stop when any iterable has been consumed
            break

def interleave(a, b):
    takelarger.threshold = 0
    return list(alternate(takelarger(a),takelarger(b)))

print(interleave(a,b))

yields

[1, 5, 7, 13, 17, 19]

I think you'll have a hard time applying numpy vectorization to this problem and maintain linear performance. This requires storing a fair bit of state: the current index in a, the current index in b, and the current threshold. numpy doesn't provide many stateful vectorized functions. In fact the only one I can think of off the top of my head is ufunc.reduce, which isn't well-suited to this problem -- though of course it could be shoehorned to work.

In fact, just after I posted this, my browser updated with an excellent vectorized solution. But that solution requires sorting, which is O(n log n); and indeed, after some testing, I see that the pure python solution below is faster for all inputs!

def interleave_monotonic(a, b):
    try:
        a = iter(a)
        threshold = next(a)
        yield threshold
        for current in b:
            if current > threshold:
                threshold = current
                yield threshold
                while current <= threshold:
                    current = next(a)
                threshold = current
                yield threshold
    except StopIteration:
        return

Note that if a is empty, this returns an empty iterable, but if b is empty, this returns a one-item iterable containing the first value of a. I think that's consistent with your example, but this is an edge case that I'm not certain about. Also, the numpy-based solution exhibits slightly different behavior, always beginning with the lesser of a[0] and b[0], while the above always begins with the first value of a, regardless. I modified the above to check for that for the following tests, which show pretty clearly that the pure python solution is the fastest.

D