def stable_sorted_copy(alist, _indices=xrange(sys.maxint)):
# the 'decorate' step: make a list such that each item
# is the concatenation of sort-keys in order of decreasing
# significance -- we'll sort this auxiliary-list
decorated = zip(alist, _indices)
# the 'sort' step: just builtin-sort the auxiliary list
decorated.sort()
# the 'undecorate' step: extract the items from the
# decorated, and now correctly sorted, auxiliary list
return [ item for item, index in decorated ]
def stable_sort_inplace(alist):
# if "inplace" sorting is desired, simplest is to assign
# to a slice-of-all-items of the original input list
alist[:] = stable_sorted_copy(alist)
