sort functions in python

[Jeff Schwab]

Carl Banks wrote:
> On Feb 8, 10:09 pm, Jeff Schwab <j... at schwabcenter.com> wrote:
>> If you expect your data to be pretty nearly sorted
>> already, but you just want to make sure (e.g. because a small number of
>> elements may have been inserted or removed since the last sort),
>> bubble-sort is a good choice.
> 
> But if you're at that stage you probably were doing something wrong in
> the first place.

How do you figure?  You don't always have control over the 
insertions/replacements, or where they happen.  As a silly example, 
assume you have a sorted list of children, by height.  Maybe you check 
your list once per school semester.  The new sort order for any given 
semester will likely be very close to the previous order; however, a few 
  swaps may be in order, according to the different speeds at which 
children have grown.

> For a list of any decent size a few insertions using a bisection
> algorithm will take fewer comparisons than a single bubblesort pass.

Do you mean that if newly inserted data are kept separate from the 
already-sorted list, then they can be merged into the list in O(log N) time?