Efficiency of Python sorted() built-in function vs. list insert() method

Question

I am not new to it, but I do not use Python much and my knowledge is rather broad and not very deep in the language, perhaps someone here more knowledgeable can answer my question. I find myself in the situation when I need to add items to a list and keep it sorted as items as added. A quick way of doing this would be.

list.append(item)                  // O(1)
list.sort()                        // ??

I would imagine if this is the only way items are added to the list, I would hope the sort would be rather efficient, because the list is sorted with each addition. However there is also this that works:

inserted = False
for i in range(len(list)):         // O(N)
    if (item < list[i]): 
        list.insert(i, item)       // ??
        inserted = True
        break
if not inserted: list.append(item)

Can anyone tell me if one of these is obviously more efficient? I am leaning toward the second set of statements, however I really have no idea.

Answer 1

What you are looking for is the bisect module and most possible the insort_left

So your expression could be equivalently written as

from

some_list.append(item)                  // O(1)
some_list.sort()                        // ??

to

bisect.insort_left(some_list, item)