Keep your lists sorted on every insert
Python is a language that provides you the tools of efficiency. The bisect module has a series of functions that work with a bisecttion algorithm. An inserting function in this grouping is the insort function which will insert an element into a sequence in the right spot according to the sort order.
from bisect import insort
sorted_list = [0, 2, 4, 6, 8, 10]
insort(sorted_list, 5)
# [0, 2, 4, 5, 6, 8, 10]The above example uses a sorted list, what if the list is not sorted?
list = [0, 4, 2, 6]
insort(list, 5)
# [0, 4, 2, 5, 6]It will still insert in the first place that it can find that makes sense. But what if there are two places that make sense? The algo seems to give up and just tack it on at the end.
list = [0, 4, 2, 6, 2]
>>> insort(list, 5)
# [0, 4, 2, 6, 2, 5]
insort works left to right but you can also work right to left with insert_right. In some cases this will be more efficient.