Python - efficiently find where something would land in a sorted list?
Question: I have a list:

    
    
    x = ['c', 'a', 'e']
    

I can sort this list:

    
    
    x_sorted = sorted(x)
    

`x_sorted` is now `['a', 'c', 'e']`

Now let's say I have a new variable `y = 'd'`

I want to find out where in `x_sorted` this new variable would fall. In this
example the new variable `y` contains the string `'d'` so it would be placed
as `['a', 'c', 'd', 'e']` in the index 2 of the list. I desire to find out
this index number as efficiently as possible (since I have to repeat this
process many times).

Here is a function I wrote which does the task very simply:

    
    
    def f(x_sorted, y):
        new_list = x_sorted[:] + [y]
        return sorted(new_list).index(y)
    

This gives me the correct answer.

I am wondering if there is a better more efficient way of doing this, as `f`
will be called 100,000+ times.

Thanks in advance!


Answer: You can use [bisect](https://docs.python.org/2/library/bisect.html)

    
    
    from bisect import bisect
    
    l = ['a', 'c', 'e']
    
    print(bisect(l,"d"))
    2
    

To add it to the list:

    
    
    from bisect import insort
    
    
    l = ['a',"b", 'c', 'e']
    
    insort(l, "d")
    print(l)
    insort(l, "f")
    print(l)
    
    ['a', 'b', 'c', 'd', 'e']
    ['a', 'b', 'c', 'd', 'e', 'f']
    

If you want a faster insert you could use a
[blist](https://pypi.python.org/pypi/blist/?) where maintaining a sorted list
with insort is:

    
    
    O(log**2 n)  vs  O(n)
    

from bisect import insort

    
    
    from blist import blist
    
    b = blist(["a", "b", "c", "e"])
    insort(b, "f")
    insort(b, "d")
    print(b)
    blist(['a', 'b', 'c', 'd', 'e', 'f'])
    

There is also a
[blist.sortedlist](http://stutzbachenterprises.com/blist/sortedlist.html#blist.sortedlist)
list where you can use
[.add](http://stutzbachenterprises.com/blist/sortedlist.html#blist.sortedlist.L.add):

    
    
    from blist import sortedlist
    
    l = ['b',"a", 'c', 'e']
    b = sortedlist(l)
    
    b.add("f")
    print(b)
    sortedlist(['a', 'b', 'c', 'e', 'f'])
    

There is also a
[sortedcontainers](http://www.grantjenks.com/docs/sortedcontainers/) library
that has a
[sortedlist](http://www.grantjenks.com/docs/sortedcontainers/sortedlist.html)
implementation.

