Python Cookbook

Sorting While Guaranteeing Sort Stability

Credit: Alex Martelli, David Goodger

Problem

You need to sort a Python list in a guaranteed-stable way (i.e., with no alteration in the relative ordering of items that compare equal).

Solution

In addition to speed, decorate-sort-undecorate (DSU) offers flexibility that sort with a comparison function argument just can’t match. For example, you can ensure the sort’s stability, as follows:

def stable_sorted_copy(alist, _indices=xrange(sys.maxint)):
    # Decorate: prepare a suitable auxiliary list
    decorated = zip(alist, _indices)

    # Sort: do a plain built-in sort on the auxiliary list
    decorated.sort(  )

    # Undecorate: extract the list from the sorted auxiliary list
    return [ item for item, index in decorated ]

def stable_sort_inplace(alist):
    # To sort in place: assign sorted result to all-list slice of original list
    alist[:] = stable_sorted_copy(alist)

Discussion

The notion of a stable sort is typically not relevant if the sequences you are sorting contain objects that are uniform in type and are simple, such as a list of integers. In such cases, objects that compare equal are equal in all measurable ways. However, in cases where equality for the sake of ordering doesn’t correspond to “deep” equality—such as tuples containing floating-point and integer numbers, or, more commonly, rich objects with arbitrary internal structure—it may matter that the elements that start off earlier in the list than their “equal” counterparts remain earlier after the sort. ...