Why is DSU decorate-sort-undecorate faster than providing a compare function?

Question

Pythonistas like to talk about a technique called DSU:

Suppose I want to sort a list by the third field's int value:

# Decorate
decorated = [(int(item[2]), item) for item in items]
# Sort
decorated.sort()
# Undecorate
items = [item[1] for item in decorated]

Supposedly, this method is much more efficient than:

def compare(item1, item2):
    return cmp(int(item1[2]), int(item2[2]))
items.sort(compare)

Why is DSU faster? What makes sort() without a comparator special?

Answer 1

It depends on how expensive the conversion from an item to value to be sorted by is. In this case, the conversion is to take the int of the third item.

With the compare method, the conversion happens multiple times per item. With the decorate/sort/undecorate method, the conversion only happens once per item. If the key function is expensive, then calling it only once per item should be more efficient.

Note that you can do the decorate/sort/undecorate approach with built-ins:

items.sort(key=lambda item: int(item[2]))