Sorting list (maybe stupid)

[Brandon Beck]

> In fact it's almost certain <wink>.  Small lists are handled by binary
> insertion sort, for peak speed, and the way that was coded just so happens
> to be stable.  That's why small examples will always lead you to believe
> .sort() is stable.  The full-blown samplesort used for non-trivial lists
> isn't stable and can't be made stable efficiently.
> 

I personally like Alex Martelli's version of a stable sort using the 
decorate-sort-undecorate idiom.  His recipe for it can be found at:

	http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/52234


The meat of his recipe is something along the lines of:

	def stable_sort_copy(alist):
		decorated = zip(alist, xrange(len(alist)))
		decorated.sort()
		return [ item for item, index in decorated ]

	def stable_sort_inplace(alist):
		alist[:] = stable_sort_copy(alist)


The efficiency of this implementation should be on the order of 
O(2*n+n*lg(n)) which we all know is O(n*lg(n)).  It's definitely not the 
most efficient way in the world to perform a stable sort, especially in 
terms of space, but it's short and sweet and lets you worry about more 
important things.  If it turns out that sorting is truly a bottleneck in 
your program, then revisit the sort for a more optimal version.