alwayssortedlist (was Re: On PEP 322 (ireverse))

[Tim Peters]

[Alex Martelli]
> ...
> [alex at lancelot bo]$ timeit.py -c -s'import bisect'
> -s'LL=range(99,0,3)' 'L=LL[:]'
>
> [alex at lancelot bo]$ timeit.py -c -s'import bisect'
> -s'LL=range(99,0,3)' 'L=LL[:]; L.append(33); L.sort()'
> 100000 loops, best of 3: 2.3 usec per loop
>
> alex at lancelot bo]$ timeit.py -c -s'import bisect' -s'LL=range(99,0,3)'
> 'L=LL[:]; bisect.insort(L, 33)'
> 100000 loops, best of 3: 4.4 usec per loop

Well, range(99,0,3) produces an empty list, so it's not timing something
interesting.  Change it to, e.g., range(0,999,3).  bisect.insort() will
eventually beat the pants off list.sort(), and the more expensive element
comparisons are, the shorter the list at which insort first wins.  Up until
that point, insort() loses just due to the overhead of calling a
coded-in-Python function.  Once enough comparison work is done to overcome
that overhead, insort wins, because list.sort() always needs at least
len(list)-1 comparisons (even if the list is already sorted), while
bisect.insort() never needs more than about log(len(list), 2) comparisons.
Both methods are stuck with an additional O(len(list)) component to shuffle
the new element into its proper position, but that goes at C speed in both
and is just a C memmove() call for insort().