sort functions in python

[Jeff Schwab]

Steven D'Aprano wrote:
> On Sat, 09 Feb 2008 13:37:23 -0800, Jeff Schwab wrote:
> 
>> 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.
> 
> You check their heights once per semester, but you're worried about an 
> extra ten or twenty microseconds to sort the data?

Are you serious?

The fact that you wouldn't use a Python script for this is what makes it 
a "silly" example in the first place.  The debate is whether Bubble Sort 
is so bad that someone should get slapped upside the head for even 
mentioning it.  I think it's a tool, like any other, and that 
occasionally it might be the right tool for the job.  Imagine that 
instead of children, we're keeping a sorted list of a very large number 
of crystals that may grow at varying speeds, and that the sizes of the 
individual crystals are polled at a rate limited by the time taken by 
the sort algorithm.

> Frankly, if we're talking about sorting at the level of Python 
> application programming, nothing you write is going to beat the speed of 
> the built-in list.sort() and sorted() built-ins.

That's probably true with five-nines probability, but there may be 
exceptions.  Do you really not understand what I'm getting at, or do you 
just disagree?