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.
``` python
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?
``` python
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.
``` python
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.
chriserin
January 24, 2019