What is the right Python idiom for sorting by a single criterion (field or key)?

Question

As in title, how can I sort objects by single criterion?

I've heard about key parameter, cmp parameter, and Decorate-Sort-Undecorate pattern.
Which one should I use in modern Python, and how?

Answer 1

In modern Python, the best way is to use list.sort or sorted with key argument.

When you pass key argument, sorting function, instead of comparing elements directly, compares whatever key returned for them.

So, you can pass as key any callable that takes element to be sorted as single positional argument, and returns what the element should be sorted by.
The callable will be called once for each element.

Some simple examples:

   list_ = ['B', 'aaa', 'CC']

   sorted(list_)
=> ['B', 'CC', 'aaa']

   # case-insensitive sorting
   sorted(list_, key=str.lower)
=> ['aaa', 'B', 'CC']

   # sorting by length
   sorted(list_, key=len)
=> ['B', 'CC', 'aaa']

Sorting with key is roughly equivalent to Decorate-Sort-Undecorate pattern:

def decorate_sort_undecorate(iterable, key):
    # 1: decorate:
    decorated = [(key(elem), index, elem) for index, elem in enumerate(iterable)]

    # 2: sort:
    decorated.sort()

    # 3: undecorate: 
    return [elem for key_, index, elem in decorated]

This creates temporary list (decorated) of 3-element tuples,
which have form: (key_, index, elem), where key_ = key(elem). Then, decorated list is sorted.
Tuples are compared by first non-equal element. This is key_, or if key_s are equal, index. Because there are no equal indexes, elements are never directly compared.
At the end, elements are extracted from decorated into new list, which is returned.

Random thoughts:

• Order of sorted elements can be reversed using reverse=True,
• lambdas and functions from operator module are often passed as key,
• before 2.4, there were no key parameter. There were only Decorate-Sort-Undecorate pattern and slow cmp parameter,
• Sorting a Python list by two criteria.