Inserting values into a sorted array

Question

What would be the quickest way to insert values into the correct position in a sorted numpy array?

For example, I would like to insert every value of binto a:

a = [1,1,2,4,7,7,11,13,13,13,15,20,25,26,27,30,45,70]

b = [5,7,9,45]

I've tried looping through a for each value of b and inserting it that way. I've also tried the bisect_left method:

for i in b:
a.insert(bisect_left(a,i),i)

Both methods are too slow as I have hundreds of thousands of data elements to go through.

Any ideas?

Answer 1

You could use searchsorted and insert:

a = numpy.array([1,1,2,4,7,7,11,13,13,13,15,20,25,26,27,30,45,70])
b = numpy.array([5,7,9,45])
ii = numpy.searchsorted(a, b)
a = numpy.insert(a, ii, b)

Answer 2

let's note n = len(a) and m = len(b),

1. you can use a binary search to find each element's position and insert it, that would done in m*n*log(n) time
2. you can merge both arrays, that would have an n+m complexity
3. you can use a specialized structure, a balanced binary tree, you can find a lot of implementation of these in python, the time complexity will be mlog(n)

Now given possible values of n and m, you can determine which solution is best, but don't expect to do better than that