sorting - Python - efficiently find where something would land in a sorted list? -

i have list:

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

i can sort list:

x_sorted = sorted(x) 

x_sorted ['a', 'c', 'e']

now let's have new variable y = 'd'

i want find out in x_sorted new variable fall. in example new variable y contains string 'd' placed ['a', 'c', 'd', 'e'] in index 2 of list. desire find out index number efficiently possible (since have repeat process many times).

here function wrote task simply:

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

this gives me correct answer.

i wondering if there better more efficient way of doing this, f called 100,000+ times.

thanks in advance!

you can use bisect

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

to add 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 want faster insert use blist maintaining sorted list 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 blist.sortedlist list can use .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 sortedcontainers library has sortedlist implementation.