Best way to insert sorted in a list

[Steven D'Aprano]

On Fri, 17 Jun 2011 13:53:10 -0700, SherjilOzair wrote:

> What has the community to say about this ? What is the best (fastest)
> way to insert sorted in a list ?

if you're doing repeated insertions into an already sorted list, there's 
no question that the bisect module is the right way to do it.

(Unless you have a very old version of Python, version 2.3 or older.)

>>> from timeit import Timer
>>> setup = """
... L = list(range(10000)) + list(range(10100, 30000))
... from bisect import insort
... def sort_insert(a, x):
...     a.append(x)
...     a.sort()
... """
>>> t_bisect = Timer("for i in range(10000, 10100): insort(L, i)", setup)
>>> t_sort = Timer("for i in range(10000, 10100): sort_insert(L, i)", setup)
>>>
>>> t_sort.timeit(number=100)
19.430757999420166
>>> t_bisect.timeit(number=100)
0.3741610050201416

(For those unfamiliar with timeit, small numbers are faster.)



-- 
Steven