>>> def multisort(xs, specs): ... for key, reverse in reversed(specs): ... xs.sort(key=attrgetter(key), reverse =reverse) ... return xs • 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. This idiom is called Decorate-Sort-Undecorate after its three steps: For example, to sort the student data by grade using the DSU approach: This idiom works because tuples are compared lexicographically; the first items are compared; if they are the same then the second items are compared, and so on. It is not strictly necessary in all cases to include the index i in the decorated list, but including it gives two benefits: Another name for this idiom is Schwartzian transform, after Randal L. Schwartz, who popularized it among Perl programmers. Now that Python sorting provides key-functions, this technique is not often needed. Many constructs given in this HOWTO assume Python 2.4 or later. Before that, there was no$_{sorted()}$ builtin and$_{list.sort()}$ took no keyword arguments. Instead, all of the Py2.x versions supported a cmp parameter to handle user specified comparison functions. In Py3.0, the cmp parameter was removed entirely (as part of a larger effort to simplify and unify the language, eliminating the conflict between rich comparisons and the$_{__cmp__()}$ magic method). In Py2.x, sort allowed an optional function which can be called for doing the comparisons. That function should take two arguments to be compared and then return a negative value for less-than, return zero if they are equal, or return a positive value for greater-than. For example, we can do: 4 7 The Old Way Using the cmp Parameter • The original items do not have to be comparable because the ordering of the decorated tuples will be determined by at most the first two items. So for example the original list could contain complex numbers which cannot be sorted directly. • The sort is stable – if two items have the same key, their order will be preserved in the sorted list. The Timsort algorithm used in Python does multiple sorts efficiently because it can take advantage of any ordering already present in a dataset. 6 The Old Way Using Decorate-Sort-Undecorate This can be abstracted out into a wrapper function that can take a list and tuples of field and order to sort them on multiple passes. >>> decorated =[(student .grade, i, student) for i, student in enumerate(student_ ↪ → objects)] >>> decorated.sort() >>> [student for grade, i, student in decorated] # undecorate [('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)] >>> multisort( list(student_objects), (( 'grade', True ), ( 'age', False ))) [('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]