DSA Sorting in Python
Built-in sorting in Python is sorting done by the sorted function and the sort method. A key function tells the sort what value to compare for each item.
sorted builds, sort changes
The sorted function builds a new list and leaves the input alone. The sort method changes its own list instead, which is called sorting in place.
fruits = ["pear", "fig", "plum"]
print(sorted(fruits))
print(fruits)
print(fruits.sort())
print(fruits)Key functions choose the order
A key function runs on each item before any comparing starts. Sorting by length and sorting by lowercase letters give different orders here.
words = ["banana", "fig", "cherry", "kiwi"]
print(sorted(words, key=len))
names = ["Bob", "alice", "Carol"]
print(sorted(names, key=str.lower))Stability with equal keys
Stability means items with equal keys keep their starting order. The output keeps amy before cy, because both share the same age key.
pairs = [("amy", 30), ("bo", 25), ("cy", 30), ("di", 25)]
print(sorted(pairs, key=lambda pair: pair[1]))A custom order with cmp_to_key
A comparator is a function that reports which of two items comes first. The cmp_to_key helper turns a comparator into a key function.
from functools import cmp_to_key
def compare(a, b):
if len(a) != len(b):
return len(a) - len(b)
if a < b:
return -1
if a > b:
return 1
return 0
words = ["pear", "fig", "plum", "kiwi", "date"]
print(sorted(words, key=cmp_to_key(compare)))Example
people = [["mia", 34], ["leo", 28], ["ava", 34], ["sam", 28], ["zoe", 34]]
by_name = sorted(people, key=lambda person: person[0])
print("by name:", by_name)
by_age = sorted(by_name, key=lambda person: person[1])
print("then by age:", by_age)
direct = sorted(people, key=lambda person: (person[1], person[0]))
print("direct:", direct)Key points
- Use sorted when the original list must stay unchanged.
- Python sorting is stable, so equal keys keep their starting order.
- Timsort is the name of the sorting method Python uses inside.
In this example, five people are sorted by age, with names in order inside each age. The first sort puts the names in alphabetical order. The second sort orders by age, and stability keeps that name order inside each age group. The direct sort with a pair key gives exactly the same final list. Stability is what makes the two-step route match the direct route.
Note
The sort method returns None, so the sorted list is the changed list itself.
Try it Yourself
Edit the code, then press Run.
Running is simulated · Python Playground
Exercise
Which call leaves the original list completely unchanged?