Custom Sorts with Lambda in Python

sorted() vs. .sort(): Two Tools for the Same Job

Python provides two ways to sort data: the sorted() built-in function and the list.sort() method. While they achieve the same result, they have one fundamental difference that's crucial to understand.

• sorted(iterable): This function takes any iterable (like a list, tuple, or string) and returns a new, sorted list, leaving the original iterable unchanged.
• list.sort(): This is a method that can only be called on a list. It sorts the list in-place, modifying the original list and returning None.

In competitive programming, you often need to preserve the original order of data for other purposes. Using sorted() is safer in those cases. However, if memory is tight and you don't need the original list, .sort() can be slightly more efficient as it avoids creating a new copy.

To see a detailed comparison with examples, let's turn to a helpful article.

Customizing Sort Order with the key Argument

The real power of Python's sorting comes from the key argument. This parameter accepts a function that will be called on every element of the list before making comparisons. The return value of this function (the "key") is what's used to sort the elements.

For example, to sort a list of strings by their length instead of alphabetically, you can use Python's built-in len function as the key:

words = ["banana", "pie", "Washington", "book"]
sorted_by_length = sorted(words, key=len)
print(sorted_by_length)
# Output: ['pie', 'book', 'banana', 'Washington']

Another common use is for case-insensitive sorting of strings, using str.lower as the key:

names = ["Alice", "bob", "Zeke", "carol"]
sorted_case_insensitive = sorted(names, key=str.lower)
print(sorted_case_insensitive)
# Output: ['Alice', 'bob', 'carol', 'Zeke']

Notice that the original values from the list are returned, not the keys themselves.

Using lambda for Ultimate Flexibility

What if your sorting logic is simple and unique to this one situation? Defining a whole new function with def for a one-off sorting key can feel clunky. This is the perfect use case for lambda functions.

A lambda function is a small, anonymous function defined without a name. The syntax is lambda arguments: expression. It's ideal for the key argument because it allows you to define your custom logic right where you need it.

For example, if you have a list of tuples (name, score) and want to sort by score, you don't need to define a separate function.

To see this in action, let's watch a short video that demonstrates using a lambda to sort a list of tuples by the second element.

This technique is incredibly common. For instance, to sort a list of astronaut names by their last name:

sorted_students = sorted(students, key=lambda s: s[1])
# sorted_students will be: [[10, 88, 19], [12, 95, 20], [11, 95, 18]]
# Note: The order of students with score 95 is not guaranteed. We'll fix this next!

Advanced Sorting: Tie-Breaking with Multiple Keys

In the exercise above, two students had the same score of 95. What if you wanted to break ties by sorting the students with the same score by their age in ascending order?

You can achieve this by having your lambda function return a tuple. Python automatically sorts by the first element of the tuple, and if they are equal, it uses the second element as a tie-breaker, and so on.

To sort by score (primary) and then age (secondary), the key would be lambda s: (s[1], s[2]).

Let's see a demonstration of this powerful technique.

Pro-Tip: Mixed Ascending and Descending Order

What if the problem requires you to sort by score in descending order, but break ties by age in ascending order?

The reverse=True argument applies to the entire sort, which isn't what we want. The trick is to negate the numerical value you want to sort in descending order within your key tuple.

For example, to sort by score (descending) and then age (ascending):

students = [[10, 88, 19], [12, 95, 20], [11, 95, 18]]

# Sort by score descending (-s[1]), then age ascending (s[2])
sorted_students = sorted(students, key=lambda s: (-s[1], s[2]))

print(sorted_students)
# Output: [[11, 95, 18], [12, 95, 20], [10, 88, 19]]

Notice how [11, 95, 18] now comes before [12, 95, 20] because 18 is less than 20. This works because sorting -95 and -88 in ascending order is equivalent to sorting 95 and 88 in descending order.

This technique is explained very well in the following article, which is written with competitive programming in mind.

Note: This negation trick only works for numeric types. You cannot put a - in front of a string.

sorted_students = sorted(students, key=lambda s: (-s[1], s[0]))
# sorted_students will be: [[11, 95, 18], [12, 95, 20], [10, 88, 19]]
# Here, the student with ID 11 comes before the student with ID 12 because they have the same score, and we sort by ID ascending as the tie-breaker.

Conclusion

You've done an excellent job today! Mastering Python's built-in sorting is a massive leap forward. It's a tool you will use in countless problems, and knowing how to tailor it to your exact needs will save you immense time and effort.

Key Takeaways:

• sorted() returns a new sorted list, while list.sort() modifies a list in-place.
• The key argument accepts a function to specify custom sorting logic.
• lambda functions are perfect for creating concise, one-off key functions.
• You can achieve multi-level sorting (tie-breaking) by returning a tuple from your lambda function.
• For mixed-order sorting, you can negate numerical values within the key tuple to sort them in descending order.

Up Next:
We've covered general-purpose comparison sorts (Merge Sort, Quicksort, and Python's built-in Timsort). However, some problems involve data with special properties that allow for even faster sorting. In the next lesson, we will explore Counting Sort, a non-comparison-based algorithm that is extremely efficient for sorting integers within a limited range.