10. Python Sorting in Practice

What you'll learn

• 1Distinguish sorted() (new list) from list.sort() (in-place)
• 2Sort by a key function — single, tuple, lambda
• 3Exploit Python's stable sort for multi-pass sorting

Overview

Python's Timsort is O(n log n), stable, and tuned for partially-sorted data. The `key` parameter handles 99% of custom sort needs — you almost never need a comparator.

Core Concepts

1. sorted vs list.sort

nums = [3, 1, 4, 1, 5]

# sorted() — returns NEW list
sorted_nums = sorted(nums)        # [1, 1, 3, 4, 5]
print(nums)                       # [3, 1, 4, 1, 5] unchanged

# list.sort() — modifies IN PLACE, returns None
nums.sort()                       # nums is now sorted
print(nums)                       # [1, 1, 3, 4, 5]

2. Reverse

sorted(nums, reverse=True)        # descending

3. key function

words = ['banana', 'apple', 'fig']
sorted(words, key=len)            # ['fig', 'apple', 'banana']
sorted(words, key=str.lower)      # case-insensitive

people = [{'name': 'Alice', 'age': 30}, {'name': 'Bob', 'age': 25}]
sorted(people, key=lambda p: p['age'])

# Sort points by (x, y)
points = [(3,1), (1,2), (3,0)]
sorted(points)                    # tuples sort lexicographically

4. Multi-key sort

# Sort by age ascending, then name descending — return a tuple from key
sorted(people, key=lambda p: (p['age'], p['name']))

# For mixed asc/desc directions, exploit stability with two passes
result = sorted(people, key=lambda p: p['name'], reverse=True)
result = sorted(result, key=lambda p: p['age'])
# Result is sorted by age asc, then name desc within each age group

5. operator.itemgetter for speed

from operator import itemgetter
sorted(records, key=itemgetter(0, 2))    # faster than lambda r: (r[0], r[2])

Examples

Example 1 — src/01_basic_sort.py

sorted() vs list.sort() side by side.

Example 2 — src/02_key_func.py

Sort strings by length, by last letter, by lowercase form.

Example 3 — src/03_multi_key.py

Multi-key sort via tuples + the two-pass trick for mixed directions.

Example 4 — src/04_stable_proof.py

Demonstrate that equal keys keep their original order (stability).

Common Mistakes

1. `x = list.sort()` assigns None. Use sorted(list) for a new list.
2. Sorting with a comparator function — Python 3 only accepts `key=`. Use functools.cmp_to_key as a last resort.
3. Mixing types (e.g. sorted([1, 'a'])) — TypeError. Provide a key.
4. Forgetting that sorted() builds a new list and uses O(n) extra space.

Recap

• sorted(): new list. list.sort(): in-place, returns None.
• Pass a `key=` function to sort by something derived.
• Tuples enable multi-key sort; stability lets you chain sorts.

Try It

1. BOJ 1181 (Word sort) — multi-key.
2. BOJ 11650 (Sort points by x then y).