One of the more unique Python idioms is the Decorate-Sort-Undecorate (DSU) sorting method used to optimize sorting performance.

PythonWiki describes it’s function as a combination of three steps:

  • First, the initial list is decorated with new values that control the sort order.
  • Second, the decorated list is sorted.
  • Finally, the decorations are removed, creating a list that contains only the initial values in the new order.

>>> words = “This is a test string from Andrew.”.split()
>>> deco = [ (word.lower(), i, word) for i, word in enumerate(words) ]
>>> deco.sort()
>>> new_words = [ word for _, _, word in deco ]
>>> print new_words
[’a', ‘Andrew.’, ‘from’, ‘is’, ’string’, ‘test’, ‘This’]

It would nice if the Python language found a way to support this type of efficiency gain in one-line syntax, but for now this is what you’ll have to do to keep your sorts optimized.