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

[Tim Peters]

[Jeremy Fincher]
> ...
> It's interesting, of course, because although the point of
> bisect.insort is to use O(log n) binary search to find the place to
> insert an element, it's still O(n) because list.insert is O(n).  So if
> timsort is close to O(n) for nearly-sorted lists, I wonder if it would
> actually be faster than bisect.insort because it's coded in C.

It can be if the list is short and/or comparison of elements is very cheap.
Comparison of any kind is much more expensive than copying a pointer, so
comparison cost eventually dominates.  No comparison-based sorting algorithm
can ever use fewer than len(list)-1 compares, because that's the minimum #
of compares needed just to determine *whether* a list is already sorted.  So
the log(len(list), 2) compares used by insort will eventually dominate the
len(list)-1 best-case compares used by list.sort(); the crossover point
depends on the expense of element comparions (e.g., comparing two ints is
pretty cheap, comparing two instances of a user-defined class with a Python
__lt__ mehod is pretty expensive).  For ints it may take a few hundred
elements before insort() clearly wins; for instances with __cmp__ or __lt__
methods written in Python it will probably only take a few dozen.