python sorted key vs comparator

When you need to sort a list with custom rules, Python's sorted() and list.sort() accept two different mechanisms: a key function and a comparator. The key parameter transforms each element before comparison, while a comparator defines a custom comparison rule. Understanding the difference between python sorted key vs comparator affects both code clarity and runtime performance.

The Two Sorting Mechanisms

Python's sorting functions rely on the natural ordering of elements when no extra arguments are given. For integers, strings, and other built-in types, that works out of the box. But when you have a list of dictionaries, objects, or tuples where the default order is not what you need, you have to tell Python how to compare elements.

The key parameter accepts a callable that takes one element and returns a sortable value. Python then sorts the list based on those returned values. The comparator approach, on the other hand, uses a function that takes two elements and returns a negative, zero, or positive number to indicate their relative order. In Python 3, the cmp parameter was removed from sorted() and list.sort(), so comparators are used through functools.cmp_to_key().

Using the key Parameter

The key parameter is the idiomatic way to sort in Python. It is concise, readable, and often faster than a comparator. Consider a list of tuples representing products with a name and a price:

products = [("laptop", 1200), ("mouse", 25), ("monitor", 300)]

# Sort by price (second element)
sorted_by_price = sorted(products, key=lambda item: item[1])
print(sorted_by_price)
# [('mouse', 25), ('monitor', 300), ('laptop', 1200)]

The lambda returns the price for each tuple, and Python sorts the tuples by that value. You can also use built-in functions as keys, like len for strings or str.lower for case-insensitive sorting.

For more complex sorting, you can return a tuple from the key function. Python compares tuples element by element, so this lets you sort by multiple criteria. For example, sort by last name, then first name:

people = [("Alice", "Smith"), ("Bob", "Jones"), ("Carol", "Smith")]
sorted_people = sorted(people, key=lambda person: (person[1], person[0]))
print(sorted_people)
# [('Bob', 'Jones'), ('Alice', 'Smith'), ('Carol', 'Smith')]

To reverse the order of one criterion, you can negate numeric values or use reverse=True for the whole sort, but that reverses all criteria. For mixed ascending/descending on numeric fields, negation works:

# Sort by price descending, then name ascending
sorted_mixed = sorted(products, key=lambda p: (-p[1], p[0]))

Using cmp_to_key for Comparators

A comparator is a function that takes two arguments and returns a negative number if the first should come before the second, zero if they are equal, and a positive number otherwise. To use a comparator with sorted(), you wrap it with functools.cmp_to_key():

from functools import cmp_to_key

def compare_products(p1, p2):
    # Compare by price, then by name
    if p1[1] != p2[1]:
        return p1[1] - p2[1]
    return (p1[0] > p2[0]) - (p1[0] < p2[0])

products = [("laptop", 1200), ("mouse", 25), ("monitor", 300)]
sorted_products = sorted(products, key=cmp_to_key(compare_products))
print(sorted_products)
# [('mouse', 25), ('monitor', 300), ('laptop', 1200)]

The comparator gives you full control over the ordering logic. This is useful when the comparison cannot be expressed as a simple key transformation, such as when the order depends on both elements in a non-transitive way or when you need to access external state.

Key vs Comparator: What Actually Differs

The most important difference is how many times each function is called. A key function is invoked exactly once per element. The resulting key values are stored and then compared using Python's built-in comparison operators. A comparator, on the other hand, is called each time two elements need to be compared during the sorting algorithm. For a list of n elements, that means roughly O(n log n) calls to the comparator.

This has two consequences. First, performance: if the key function is cheap, using key is almost always faster because it reduces the work to O(n) plus the cost of comparing simple keys. Second, side effects: because a comparator is called many times, it must be pure and deterministic. A key function is also expected to be pure, but it is called fewer times, so accidental side effects are less likely to cause subtle bugs.

Another difference is readability. A key function often expresses the intent directly: "sort by this attribute." A comparator requires you to read the logic and understand the sign convention. For most sorting needs, key leads to clearer code.

Performance and Runtime Behavior

To illustrate the runtime cost, consider sorting a list of 10,000 random integers with a key that computes the absolute value versus a comparator that does the same. The key version calls the absolute value function 10,000 times. The comparator version calls the absolute value function roughly 10,000 * log2(10,000) ≈ 133,000 times, because each comparison may call it twice. Even if the function is trivial, the overhead adds up.

For expensive key functions, the difference is even more pronounced. A key function that parses a string or fetches a database field is called once per element. The same logic inside a comparator would be repeated many times, potentially causing significant slowdowns.

There is also a memory consideration. The key approach stores the computed keys in a temporary list, which uses O(n) extra memory. The comparator approach does not store keys, but it pays for repeated computation. In practice, the extra memory for keys is usually negligible compared to the performance gain.

Python's Timsort, the algorithm behind sorted() and list.sort(), is adaptive and takes advantage of existing order. Both key and cmp_to_key work with Timsort, but the key-based approach allows Timsort to compare simple values, which are often faster to compare than custom objects.

Choosing Between key and Comparator

Use key whenever you can derive a sortable value from each element. This covers the vast majority of sorting tasks: sorting by an attribute, by a computed property, by a tuple of attributes, or by a normalized form of the data. The code is shorter, faster, and easier to maintain.

Use a comparator only when the comparison logic cannot be reduced to a key. Examples include:

• The order depends on the relationship between two elements, not just their individual properties.
• You need to implement a custom ordering that is not transitive, though such orderings are rare and often indicate a design problem.
• You are porting code from a language that uses comparators, such as Java or C++, and you want to keep the same logic.

In those cases, cmp_to_key gives you the flexibility you need. However, be aware that it is not the Pythonic way and comes with a performance penalty. Before reaching for a comparator, consider whether you can express the same ordering with a key function and a tuple, possibly using negation or a custom wrapper class.

Edge Cases and Limitations

One limitation of key is that it cannot handle comparisons that depend on external state that changes during the sort. For example, if you want to sort based on the distance to a point that moves during sorting, a key function would compute the distance once and become stale. A comparator could re-evaluate the distance each time, but that would be both incorrect and slow if the state changes mid-sort. In practice, such scenarios are rare and usually indicate a need to rethink the algorithm.

Another edge case is sorting objects that do not have a natural ordering and where the key function returns objects that themselves cannot be compared. For instance, if you try to sort a list of dictionaries by a key that returns another dictionary, Python will raise a TypeError because dictionaries are not orderable. You must ensure that the key returns a comparable type, such as a number, string, or tuple of comparable values.

Comparators also have a subtle requirement: they must be consistent. If the comparator returns inconsistent results for the same pair of elements (e.g., due to floating-point rounding or mutable state), the sort may produce unpredictable results or even raise an error. The key approach avoids this because each element is reduced to a fixed key once.

Finally, remember that cmp_to_key is not a drop-in replacement for a key function. It wraps the comparator into a class that implements the rich comparison methods, but it still calls your comparator for every comparison. If you are migrating from Python 2 code that used the cmp parameter, you can use cmp_to_key as a direct translation, but you should consider rewriting the logic with a key function for better performance and readability.