Sorting in Real Life: sorted() and key

Just use the built-in

Python's sorted() and list.sort() use Timsort, a clever mix of merge sort and insertion sort. It's O(n log n) and very well tested. In real code, use it.

nums = [5, 2, 9, 1]
print(sorted(nums))                 # new sorted list
print(sorted(nums, reverse=True))
nums.sort()                         # sorts the list itself
print(nums)

Output

[1, 2, 5, 9]
[9, 5, 2, 1]
[1, 2, 5, 9]

Sorting by a key

key is a function that says what to sort by:

words = ["banana", "Kiwi", "apple", "fig"]
print(sorted(words, key=len))             # by length
print(sorted(words, key=str.lower))       # ignore capitals

students = [("Asha", 91), ("Ravi", 78), ("Meera", 91), ("Arjun", 85)]
print(sorted(students, key=lambda s: s[1], reverse=True))
print(sorted(students, key=lambda s: (-s[1], s[0])))   # marks high->low, then name A->Z

Output

['fig', 'Kiwi', 'apple', 'banana']
['apple', 'banana', 'fig', 'Kiwi']
[('Asha', 91), ('Meera', 91), ('Arjun', 85), ('Ravi', 78)]
[('Asha', 91), ('Meera', 91), ('Arjun', 85), ('Ravi', 78)]

Stable sorting

A sort is stable if items that tie keep their original order. Python's sort is stable: in the third line above, Asha stays before Meera because she came first.

Common mistake: nums.sort() returns None. Writing nums = nums.sort() throws your list away! Use sorted(nums) when you want a new list back.