sort functions in python

[Jeff Schwab]

Steven D'Aprano wrote:
> On Fri, 08 Feb 2008 17:00:27 -0800, t3chn0n3rd wrote:
> 
>> Do you think it is relatively easy to write sort algorithms such as the
>> common Bubble sort in Python as compared to other high level programming
>> langauges
> 
> 
> You realise that bubble sort is one of the worst possible sort algorithms 
> possible, particularly on modern hardware? It's not the worst: bogo sort 
> and bozo sort are worse, but bubble sort is still pretty atrocious.

That's the conventional wisdom, mostly because CS professors need a "bad 
algorithm" to show undergrads, but it's not really accurate.  The truth 
is that bubble-sort's performance depends strongly on the input data. 
In the worst case, yes, bubble-sort is O(n^2); however, for 
almost-sorted data (only a few elements out of place), bubble-sort is 
actually one of the fastest known algorithms.  For already-sorted data, 
bubble-sort is O(n).  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.