Sorting Basics

The Idea

Every comparison sort works by comparing pairs and rearranging them. Judge one on three things: time, extra memory, and stability. A stable sort keeps equal items in the order they arrived.

Real-World Example

Sort a spreadsheet by name, then sort it again by city. With a stable sort the names inside each city stay alphabetical; with an unstable one that earlier work is scrambled. Stability is what makes layered sorting possible at all.

The Code

people = [("Ada", "Rome"), ("Bo", "Lima"), ("Cy", "Rome")]

# Python's sort is stable: equal keys keep their original order
by_city = sorted(people, key=lambda p: p[1])
print(by_city)
# [('Bo', 'Lima'), ('Ada', 'Rome'), ('Cy', 'Rome')]
# Ada still comes before Cy, exactly as in the input.

nums = [5, 1, 4]
nums.sort()          # sorts in place, O(n log n)
print(nums)          # [1, 4, 5]

pairs = [("x", 2), ("y", 1), ("z", 2)]
out = sorted(pairs, key=lambda p: p[1])
print([p[0] for p in out])