Chapter 19: Searching and Sorting: Classic Algorithms

"Indeed, I believe that virtually every important aspect of programming arises somewhere in the context of sorting or searching!" — Donald Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching

Chapter Overview

You've learned to measure how algorithms grow (Chapter 17) and to think recursively (Chapter 18). Now we put both skills to work on two problems that sit at the heart of virtually every software system on Earth: searching — finding a specific item in a collection — and sorting — putting items in order.

These aren't abstract exercises. Every time you search for a contact on your phone, every time a spreadsheet sorts rows by date, every time a database answers a query — searching and sorting algorithms are running behind the scenes. Google handles more than 5 trillion searches a year — roughly 14 billion a day. Amazon sorts millions of products by relevance, price, and rating. Your email app sorts messages by date, and then searches them when you type in the search bar. These two operations are so fundamental that getting them right — or wrong — can mean the difference between a program that feels instant and one that takes minutes.

In this chapter, you'll build five classic algorithms from scratch, trace through them step by step, measure their performance empirically, and then learn why Python's built-in sorting is almost always the right choice for production code. By the end, you'll understand not just how these algorithms work, but why they work, and when to reach for each one.

In this chapter, you will learn to: - Search through data with linear search (O(n)) and binary search (O(log n)) - Sort data with selection sort, insertion sort, and merge sort - Use Python's sorted(), .sort(), key functions, and lambda expressions - Compare algorithms by time complexity, space complexity, and stability - Make informed decisions about which algorithm fits a given problem

🏃 Fast Track: If you're comfortable with basic list operations from Chapter 8, skim sections 19.1–19.2 quickly and start at 19.3 (Binary Search), where the real algorithmic thinking begins.

🔬 Deep Dive: After this chapter, explore Python's bisect module in the standard library — it provides highly optimized binary search operations that professional Python developers use in production.

🧩 Productive Struggle: How Do You Sort?

Before we look at any algorithms, try this exercise. It takes two minutes, and it will change how you read the rest of this chapter.

Grab a deck of 10 playing cards (or write the numbers 1–10 on scraps of paper, shuffle them, and lay them face-up in a row).

Now sort them from lowest to highest. Pay attention to how you do it — not just the result.

Ask yourself: - Did you scan through the whole row looking for the smallest card first? That's selection sort. - Did you pick up cards one at a time and slide each into its correct position among the cards you'd already sorted? That's insertion sort. - Did you split the row in half, sort each half, and then merge the two sorted halves together? That's merge sort.

Most people instinctively use insertion sort — it's the strategy that feels most natural with physical objects. But as you'll see, what works well for 10 cards doesn't necessarily scale to 10 million records. That tension between intuition and scalability is what algorithm design is all about.

19.1 The Search Problem

Searching means finding a target value within a collection of data — or determining that it doesn't exist. This sounds simple, but it's one of the most frequently performed operations in all of computing.

Think about how often you search: - Looking up a word in a dictionary - Finding a contact in your phone - Checking whether a username is already taken - Locating a student's record in a database

🔗 Connection to Chapter 8: You've already used Python's in operator to search lists: if "potion" in inventory:. Under the hood, Python performs a linear search — it checks each element one by one. In this chapter, we'll implement that search ourselves, understand its cost, and then learn a dramatically faster alternative.

The question isn't whether you can search a collection — it's how fast. For a list of 10 items, any approach works. For a list of 10 million items, the difference between a good algorithm and a bad one can be the difference between a response in milliseconds and a response in minutes.

19.2 Linear Search

The simplest search strategy is to start at the beginning and check every element until you find the target or run out of elements. This is called linear search (also known as sequential search).

def linear_search(data: list, target) -> int:
    """Return the index of target in data, or -1 if not found."""
    for i in range(len(data)):
        if data[i] == target:
            return i      # Found it — return the index
    return -1             # Exhausted the list — not found


# --- Demo ---
scores = [78, 95, 62, 88, 73, 91, 84]

print(linear_search(scores, 88))   # 3
print(linear_search(scores, 100))  # -1
print(linear_search(scores, 78))   # 0

How It Works

Linear search walks through the list from index 0 to index len(data) - 1. At each position, it compares the current element to the target. If there's a match, it immediately returns the index. If the loop finishes without finding the target, it returns -1 (a common convention meaning "not found").

Time Complexity

🔗 Connection to Chapter 17: We analyzed growth rates with Big-O notation. Linear search is O(n) — in the worst case, you check every single element.

When Linear Search Is the Right Choice

Linear search gets a bad reputation because it's "slow," but it's the right tool in several situations:

1. The data is unsorted. If the data isn't sorted, linear search is your only option (without sorting first).
2. The list is small. For a few dozen items, a linear scan finishes so fast that keeping the data sorted (and writing trickier code) buys you nothing you'd notice.
3. You search only once. If you're going to search a list a single time, sorting it first (O(n log n)) and then binary searching (O(log n)) is actually slower overall than just doing one linear search (O(n)).
4. The data changes frequently. If elements are constantly being added and removed, maintaining sorted order is expensive.

💡 Intuition: Linear search is like reading a book page by page looking for a specific paragraph. It's tedious but reliable — and if the book isn't organized, it's your only option.

19.3 Binary Search

Now imagine you're looking up a word in a physical dictionary. You don't start at page 1 and read every entry. You open the dictionary roughly in the middle, check whether your word comes before or after that page, and then repeat the process on the appropriate half. Each step eliminates half of the remaining pages.

That's binary search — and it's dramatically faster than linear search.

The catch: binary search only works on sorted data. If the data isn't sorted, binary search produces garbage results.

def binary_search(data: list, target) -> int:
    """Return the index of target in sorted data, or -1 if not found.

    Prerequisite: data must be sorted in ascending order.
    """
    low = 0
    high = len(data) - 1

    while low <= high:
        mid = (low + high) // 2
        if data[mid] == target:
            return mid          # Found it
        elif data[mid] < target:
            low = mid + 1       # Target is in the right half
        else:
            high = mid - 1      # Target is in the left half

    return -1                   # Not found


# --- Demo ---
sorted_scores = [62, 73, 78, 84, 88, 91, 95]

print(binary_search(sorted_scores, 88))   # 4
print(binary_search(sorted_scores, 100))  # -1
print(binary_search(sorted_scores, 62))   # 0

Tracing Through an Example

Let's trace binary_search([62, 73, 78, 84, 88, 91, 95], 88) step by step:

Step 1: low=0, high=6, mid=3 → data[3]=84 < 88 → search right half
        [62, 73, 78, 84, 88, 91, 95]
                        ^mid
        84 < 88, so low = 4

Step 2: low=4, high=6, mid=5 → data[5]=91 > 88 → search left half
        [62, 73, 78, 84, 88, 91, 95]
                                ^mid
        91 > 88, so high = 4

Step 3: low=4, high=4, mid=4 → data[4]=88 == 88 → FOUND! Return 4
        [62, 73, 78, 84, 88, 91, 95]
                            ^mid
        88 == 88, found at index 4

Three comparisons to find the target in a list of 7 elements. (We count each look at a middle element as one comparison, even though the code may test it with both == and <.) Linear search would have needed 5 comparisons (checking indices 0 through 4). The difference becomes staggering with larger data:

Binary search is O(log n). Every step cuts the problem in half, so even for a billion elements, you need at most about 30 comparisons.

🐛 Debugging Walkthrough: Binary Search Off-by-One Errors

Binary search is notoriously tricky to implement correctly. As Jon Bentley pointed out in Programming Pearls (drawing on Donald Knuth's history of the algorithm), the first binary search was published in 1946, but the first version that worked correctly for every list size didn't appear until 1962 — sixteen years later. Here are the three most common mistakes:

Bug 1: Using < instead of <= in the loop condition

# WRONG — misses the case where low == high
while low < high:      # Bug: should be low <= high
    mid = (low + high) // 2
    if data[mid] == target:
        return mid
    elif data[mid] < target:
        low = mid + 1
    else:
        high = mid - 1

If the target is the only element left (low == high), this loop exits without checking it. The fix: use while low <= high.

Bug 2: Forgetting + 1 or - 1 when updating low and high

# WRONG — causes infinite loop
low = mid       # Bug: should be mid + 1
high = mid      # Bug: should be mid - 1

If low = mid (without the + 1), the search window never shrinks when low == mid, creating an infinite loop. Always skip past mid since you've already checked it: low = mid + 1 or high = mid - 1.

Bug 3: Integer overflow in mid calculation (not a Python problem)

In languages like C and Java, integers have a fixed size, so (low + high) can overflow when both are large. This isn't hypothetical: Joshua Bloch reported in 2006 that the binary search in Java's own standard library had carried exactly this bug for about nine years. The safe formula is low + (high - low) // 2. Python integers have arbitrary precision, so (low + high) // 2 is fine here — but remember the safe version if you write binary search in another language.

⚠️ Pitfall: The number one binary search bug: calling it on unsorted data. Binary search assumes sorted order. If the data isn't sorted, it will return wrong answers without any error message. Always sort first, or verify that the data is already sorted.

In real code, you'd usually reach for the standard library's bisect module instead of writing the loop yourself. bisect.bisect_left(data, target) returns the position where target is — or where it would go to keep the list sorted — so you just check that spot:

import bisect

def bisect_search(data: list, target) -> int:
    """Binary search using the standard library."""
    i = bisect.bisect_left(data, target)   # where target is, or would go
    if i < len(data) and data[i] == target:
        return i
    return -1

print(bisect_search(sorted_scores, 88))   # 4
print(bisect_search(sorted_scores, 80))   # -1 (80 would go at index 3)

🔄 Check Your Understanding #1

A sorted list has 1,024 elements. What is the maximum number of comparisons binary search needs to find a target (or determine it's not present)?

19.4 The Sorting Problem

Sorting means arranging elements in a defined order — typically ascending (smallest to largest) or descending (largest to smallest). It's one of the most studied problems in computer science, and for good reason: sorting is a prerequisite for binary search, and organized data is easier to analyze, display, and process.

Real-world sorting examples are everywhere: - Sorting students by GPA to determine class rank - Sorting products by price on an e-commerce site - Sorting emails by date (newest first) - Sorting search results by relevance - Elena's nonprofit: sorting donors by total contribution to identify top supporters

🔗 Connection to Chapter 17: Sorting is where Big-O analysis really shines. The difference between an O(n²) sort and an O(n log n) sort is the difference between a program that handles 10,000 records in seconds and one that takes hours.

We'll implement three sorting algorithms, each representing a different strategy and complexity level.

19.5 Selection Sort

Selection sort works by repeatedly finding the smallest element in the unsorted portion and moving it to the front.

The algorithm: 1. Find the smallest element in the entire list. Swap it with the element at index 0. 2. Find the smallest element in the remaining list (indices 1 onward). Swap it with the element at index 1. 3. Repeat until the entire list is sorted.

def selection_sort(data: list) -> list:
    """Sort a list in ascending order using selection sort.

    Sorts in place and returns the list.
    """
    n = len(data)
    for i in range(n - 1):
        # Find the index of the minimum element in data[i:]
        min_index = i
        for j in range(i + 1, n):
            if data[j] < data[min_index]:
                min_index = j
        # Swap the minimum element with data[i]
        data[i], data[min_index] = data[min_index], data[i]
    return data


# --- Demo ---
numbers = [64, 25, 12, 22, 11]
print(f"Before: {numbers}")
selection_sort(numbers)
print(f"After:  {numbers}")
# Before: [64, 25, 12, 22, 11]
# After:  [11, 12, 22, 25, 64]

Tracing Through Selection Sort

Let's trace selection_sort([64, 25, 12, 22, 11]):

Pass 1: Find min in [64, 25, 12, 22, 11] → 11 at index 4
        Swap data[0] and data[4]
        Result: [11, 25, 12, 22, 64]
                 ✓

Pass 2: Find min in [25, 12, 22, 64] → 12 at index 2
        Swap data[1] and data[2]
        Result: [11, 12, 25, 22, 64]
                 ✓   ✓

Pass 3: Find min in [25, 22, 64] → 22 at index 3
        Swap data[2] and data[3]
        Result: [11, 12, 22, 25, 64]
                 ✓   ✓   ✓

Pass 4: Find min in [25, 64] → 25 at index 3
        Already in place (the code swaps data[3] with itself — no change)
        Result: [11, 12, 22, 25, 64]
                 ✓   ✓   ✓   ✓   ✓

Analysis

Selection sort always performs the same number of comparisons regardless of the input: (n-1) + (n-2) + ... + 1 = n(n-1)/2. For our 5-element list, that's 4 + 3 + 2 + 1 = 10 comparisons. Even if the list is already sorted, it still scans through every unsorted element to confirm the minimum.

What does "not stable" look like? Sort [(2, "a"), (2, "b"), (1, "c")] by the number only. Pass 1 finds the minimum, (1, "c"), and swaps it with (2, "a") at the front, flinging (2, "a") to the back: [(1, "c"), (2, "b"), (2, "a")]. The two 2s have traded places, and nothing later puts them back, because as far as the sort is concerned they're equal. That long-distance swap is what breaks stability. (Insertion sort only ever slides an element past strictly larger neighbors, so equal elements never leapfrog each other.)

Selection sort is simple to understand and implement, which makes it a great teaching tool. It has one genuine strength: it makes at most n − 1 swaps, which can matter when moving data is far more expensive than comparing it. But O(n²) comparisons make it impractical for large datasets.

19.6 Insertion Sort

Insertion sort builds the sorted list one element at a time by inserting each new element into its correct position among the already-sorted elements. This is the strategy most people use when sorting a hand of playing cards.

def insertion_sort(data: list) -> list:
    """Sort a list in ascending order using insertion sort.

    Sorts in place and returns the list.
    """
    for i in range(1, len(data)):
        key = data[i]
        j = i - 1
        # Shift elements that are greater than key to the right
        while j >= 0 and data[j] > key:
            data[j + 1] = data[j]
            j -= 1
        data[j + 1] = key
    return data


# --- Demo ---
numbers = [64, 25, 12, 22, 11]
print(f"Before: {numbers}")
insertion_sort(numbers)
print(f"After:  {numbers}")
# Before: [64, 25, 12, 22, 11]
# After:  [11, 12, 22, 25, 64]

How It Works

Starting from the second element (index 1), each element is compared with the elements to its left. Elements larger than the current value are shifted one position to the right, making room for the current value to be inserted in its correct position.

Start:  [64, 25, 12, 22, 11]

i=1: key=25, compare with 64 → shift 64 right, insert 25
     [25, 64, 12, 22, 11]
      ✓   ✓

i=2: key=12, compare with 64 → shift, compare with 25 → shift, insert 12
     [12, 25, 64, 22, 11]
      ✓   ✓   ✓

i=3: key=22, compare with 64 → shift, compare with 25 → shift,
     compare with 12 → stop, insert 22
     [12, 22, 25, 64, 11]
      ✓   ✓   ✓   ✓

i=4: key=11, shift 64, shift 25, shift 22, shift 12, insert 11
     [11, 12, 22, 25, 64]
      ✓   ✓   ✓   ✓   ✓

Why Insertion Sort Matters

Insertion sort has a secret superpower: it's adaptive. Its performance depends on how sorted the data already is.

For nearly sorted data — like a list where only a few elements are out of place — insertion sort is extremely fast, approaching O(n). It's also hard to beat on very short lists, because it has almost no overhead. Those two properties make it a useful building block inside more complex algorithms (as we'll see with Python's Timsort in section 19.8).

💡 Intuition: Insertion sort is like the way you sort playing cards. You pick up each card and slide it into its correct position among the cards already in your hand. For a few cards, this is the fastest and most natural approach. For a thousand cards, you'd want a different strategy.

🔄 Check Your Understanding #2

You have a list of 1,000 elements that is already sorted except for one element that was appended to the end. Which sorting algorithm — selection sort or insertion sort — would handle this situation better, and why?

19.7 Merge Sort

Selection sort and insertion sort are both O(n²) in the worst case. Can we do better? Yes — dramatically. Merge sort uses the divide-and-conquer strategy from Chapter 18 to achieve O(n log n) time complexity.

The idea: 1. Divide: Split the list in half. 2. Conquer: Recursively sort each half. 3. Combine: Merge the two sorted halves into one sorted list.

🔗 Connection to Chapter 18: Merge sort is a textbook example of recursion. Each recursive call sorts a smaller sublist. The base case is a list of 0 or 1 elements — already sorted by definition. If the idea of "trusting the recursion" still feels shaky, revisit the leap of faith in section 18.9 before continuing.

def merge_sort(data: list) -> list:
    """Sort a list in ascending order using merge sort.

    Returns a new sorted list (does not modify the original).
    """
    # Base case: a list of 0 or 1 elements is already sorted
    if len(data) <= 1:
        return data

    # Divide: split the list in half
    mid = len(data) // 2
    left = merge_sort(data[:mid])    # Recursively sort left half
    right = merge_sort(data[mid:])   # Recursively sort right half

    # Combine: merge the two sorted halves
    return merge(left, right)


def merge(left: list, right: list) -> list:
    """Merge two sorted lists into a single sorted list."""
    result = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    # One of the lists may have remaining elements
    result.extend(left[i:])
    result.extend(right[j:])
    return result


# --- Demo ---
numbers = [64, 25, 12, 22, 11]
sorted_numbers = merge_sort(numbers)
print(f"Original:  {numbers}")
print(f"Sorted:    {sorted_numbers}")
# Original:  [64, 25, 12, 22, 11]
# Sorted:    [11, 12, 22, 25, 64]

Tracing Through Merge Sort

Let's trace merge_sort([38, 27, 43, 3, 9, 82, 10]):

merge_sort([38, 27, 43, 3, 9, 82, 10])
├── merge_sort([38, 27, 43])
│   ├── merge_sort([38])          → [38]          (base case)
│   └── merge_sort([27, 43])
│       ├── merge_sort([27])      → [27]          (base case)
│       └── merge_sort([43])      → [43]          (base case)
│       └── merge([27], [43])     → [27, 43]
│   └── merge([38], [27, 43])     → [27, 38, 43]
└── merge_sort([3, 9, 82, 10])
    ├── merge_sort([3, 9])
    │   ├── merge_sort([3])       → [3]           (base case)
    │   └── merge_sort([9])       → [9]           (base case)
    │   └── merge([3], [9])       → [3, 9]
    └── merge_sort([82, 10])
        ├── merge_sort([82])      → [82]          (base case)
        └── merge_sort([10])      → [10]          (base case)
        └── merge([82], [10])     → [10, 82]
    └── merge([3, 9], [10, 82])   → [3, 9, 10, 82]
└── merge([27, 38, 43], [3, 9, 10, 82]) → [3, 9, 10, 27, 38, 43, 82]

The key insight: the merge function does the real work. It takes two already-sorted lists and combines them into one sorted list in O(n) time by comparing the front elements of each list.

Here's the final merge in slow motion. Each step compares the two front items and takes the smaller one:

left = [27, 38, 43]   right = [3, 9, 10, 82]
27 vs 3  → take 3      result: [3]
27 vs 9  → take 9      result: [3, 9]
27 vs 10 → take 10     result: [3, 9, 10]
27 vs 82 → take 27     result: [3, 9, 10, 27]
38 vs 82 → take 38     result: [3, 9, 10, 27, 38]
43 vs 82 → take 43     result: [3, 9, 10, 27, 38, 43]
left is empty → extend with the rest of right: [3, 9, 10, 27, 38, 43, 82]

Why O(n log n)?

Look at the call tree level by level. At the top, one merge combines n elements. One level down, two merges combine n/2 elements each — n in total again. Every level does about n work, no matter how the pieces are split. How many levels are there? You keep halving until the pieces have size 1, which takes about log₂ n halvings (the same count as binary search). So the total is roughly n work per level × log₂ n levels = O(n log n). For a million elements, that's about 20 levels of a million steps each — 20 million, instead of the roughly 500 billion comparisons selection sort needs.

Analysis

The trade-off: merge sort is much faster than selection sort and insertion sort for large datasets, but it uses O(n) extra memory. Selection sort and insertion sort work in-place — they rearrange elements within the original list without allocating significant extra memory.

💡 Intuition: Merge sort is like organizing a messy pile of exams. You split the pile in half, have two friends each sort their half, and then you merge the two sorted piles by repeatedly comparing the top exam of each pile and taking whichever comes first. Each person does the same thing recursively — splitting their pile and getting help — until someone has just one exam (which is "sorted" by definition).

19.8 Python's Built-in Sorting

Now that you understand how sorting algorithms work internally, here's the practical reality: in production Python code, you should almost always use the built-in sorting functions. They're implemented in highly optimized C code using an algorithm called Timsort, and they'll outperform anything you write in pure Python.

sorted() vs. .sort()

Python provides two ways to sort:

# sorted() — returns a NEW sorted list, original unchanged
original = [64, 25, 12, 22, 11]
result = sorted(original)
print(f"original: {original}")   # [64, 25, 12, 22, 11]
print(f"result:   {result}")     # [11, 12, 22, 25, 64]

# .sort() — sorts IN PLACE, returns None
numbers = [64, 25, 12, 22, 11]
return_value = numbers.sort()
print(f"numbers:      {numbers}")       # [11, 12, 22, 25, 64]
print(f"return_value: {return_value}")  # None

⚠️ Pitfall: A classic bug: result = my_list.sort(). Since .sort() returns None, result will be None — not the sorted list. Use sorted() when you need the result as a return value, and .sort() when you want to modify the list in place.

The reverse Parameter

Both functions accept reverse=True for descending order:

scores = [78, 95, 62, 88, 73]

ascending = sorted(scores)
descending = sorted(scores, reverse=True)

print(ascending)    # [62, 73, 78, 88, 95]
print(descending)   # [95, 88, 78, 73, 62]

Key Functions: Custom Sort Order

The key parameter lets you specify what to sort by. It takes a function that transforms each element into a sort key:

# Sort strings by length
words = ["banana", "pie", "strawberry", "kiwi", "fig"]
by_length = sorted(words, key=len)
print(by_length)    # ['pie', 'fig', 'kiwi', 'banana', 'strawberry']

# Sort strings case-insensitively
names = ["Charlie", "alice", "Bob", "diana"]
by_name = sorted(names, key=str.lower)
print(by_name)      # ['alice', 'Bob', 'Charlie', 'diana']

Lambda Expressions

For simple key functions, lambda expressions provide a compact, inline syntax:

# lambda parameter: expression
# Equivalent to a one-line function that returns the expression

# Sort a list of tuples by the second element
students = [("Alice", 3.8), ("Bob", 3.5), ("Charlie", 3.9), ("Diana", 3.7)]
by_gpa = sorted(students, key=lambda student: student[1], reverse=True)
print(by_gpa)
# [('Charlie', 3.9), ('Alice', 3.8), ('Diana', 3.7), ('Bob', 3.5)]

A lambda is just a small anonymous function. lambda student: student[1] is equivalent to:

def get_gpa(student):
    return student[1]

You met this syntax briefly in Chapter 8. Here are the rules that matter:

• One expression, no statements. The body is a single expression, and its value is returned automatically: no return keyword, no if statement, no loops, no assignments. (A conditional expression like lambda t: t["due"] if t["due"] else "9999-12-31" is fine, and you'll see one in the project checkpoint.)
• Use it inline, where it's needed. Lambdas shine as throwaway arguments to sorted(), .sort(), min() and max(). If you catch yourself writing get_gpa = lambda s: s[1], write a def instead: you get a real name in error messages and room for a docstring. (PEP 8, Python's style guide, says the same.)
• If it's getting long, it should be a def. A lambda that needs a comment to explain it has outgrown itself.

💡 Tip: For the very common "sort by position 1" or "sort by the 'gpa' field" cases, the standard library's operator.itemgetter(1) and operator.itemgetter("gpa") build the same key function for you. You'll see both styles in real code.

Here's the grade calculator example — sorting students by GPA and finding a specific student with binary search:

students = [
    {"name": "Alice", "gpa": 3.8},
    {"name": "Bob", "gpa": 3.5},
    {"name": "Charlie", "gpa": 3.9},
    {"name": "Diana", "gpa": 3.7},
    {"name": "Eve", "gpa": 3.6},
]

# Sort by GPA descending (class rank)
ranked = sorted(students, key=lambda s: s["gpa"], reverse=True)
for i, student in enumerate(ranked, 1):
    print(f"#{i}: {student['name']} — GPA {student['gpa']}")
# #1: Charlie — GPA 3.9
# #2: Alice — GPA 3.8
# #3: Diana — GPA 3.7
# #4: Eve — GPA 3.6
# #5: Bob — GPA 3.5

Multi-Key Sorting

You can sort by multiple criteria using tuples as keys:

tasks = [
    ("Buy groceries", 2, "2025-03-15"),
    ("Call dentist", 1, "2025-03-14"),
    ("Study Python", 1, "2025-03-16"),
    ("Do laundry", 3, "2025-03-14"),
    ("Pay rent", 1, "2025-03-14"),
]

# Sort by priority first (ascending), then by date
by_priority_date = sorted(tasks, key=lambda t: (t[1], t[2]))
for task in by_priority_date:
    print(f"  Priority {task[1]}: {task[0]} (due {task[2]})")
# Priority 1: Call dentist (due 2025-03-14)
# Priority 1: Pay rent (due 2025-03-14)
# Priority 1: Study Python (due 2025-03-16)
# Priority 2: Buy groceries (due 2025-03-15)
# Priority 3: Do laundry (due 2025-03-14)

Python compares tuples element by element: first the priorities, and only if those tie, the dates. Notice that "Call dentist" and "Pay rent" tie on both keys, so they stay in their original order — that's stability at work.

What if you want priority ascending but dates newest first? For numbers you can negate inside the key (-t[1]), but you can't negate a string. Instead, use stability: sort by the secondary key first, then by the primary key. The second sort keeps the first sort's order wherever the primary keys tie:

newest_first = sorted(tasks, key=lambda t: t[2], reverse=True)   # secondary key first
result = sorted(newest_first, key=lambda t: t[1])                # then primary key
for task in result:
    print(f"  Priority {task[1]}: {task[0]} (due {task[2]})")
# Priority 1: Study Python (due 2025-03-16)
# Priority 1: Call dentist (due 2025-03-14)
# Priority 1: Pay rent (due 2025-03-14)
# Priority 2: Buy groceries (due 2025-03-15)
# Priority 3: Do laundry (due 2025-03-14)

What Is Timsort?

Python's built-in sort uses Timsort, designed by Tim Peters in 2002 specifically for Python. Timsort is a hybrid algorithm that combines the best properties of merge sort and insertion sort:

1. It scans the data for runs — stretches that are already in order. (A descending run is simply reversed.) Real-world data is full of these.
2. If a run is very short, it extends it to a minimum length (typically 32 to 64 items) using insertion sort, which is fast on small pieces.
3. It merges the runs together, merge-sort style, with extra tricks for when one run keeps "winning."

Because it finds existing order instead of ignoring it, Timsort is O(n) in the best case (already-sorted data — one big run, nothing to merge) and O(n log n) in the worst case. It's also stable — equal elements maintain their original relative order. This combination of properties, plus its C implementation, makes it nearly impossible to beat in practice. (Since Python 3.11, CPython uses a smarter rule for choosing which runs to merge next, called Powersort, but the run-finding and merging ideas are the same.)

⚠️ Two meanings of "in place": .sort() sorts in place in the everyday sense — it changes your list instead of handing you a new one. But in the algorithm-analysis sense ("uses only O(1) extra memory"), Timsort is not in-place, because it borrows temporary space while merging. That's why the comparison table below lists Timsort as "No" in the In-place column.

✅ Best Practice: Unless you're in a CS algorithms course (like right now), use sorted() or .sort(). They're faster, better tested, and more readable than hand-rolled sorting code. Understanding how sorting works is essential for making informed decisions. Reimplementing sorting in production code is almost always a mistake.

19.9 Comparing Algorithms

Let's put all our algorithms side by side, both theoretically and empirically.

The Comparison Table

Key Trade-offs

• Selection sort is the simplest to understand but always does O(n²) work. Use it only for very small lists, or when writes are so expensive that its minimal number of swaps matters.
• Insertion sort is excellent for small or nearly-sorted data. It's in-place, stable, and adaptive.
• Merge sort guarantees O(n log n) regardless of input but requires O(n) extra memory. It's the go-to when you need predictable performance.
• Timsort combines the best of insertion sort and merge sort. Use it. It's built into Python.

Empirical Timing

Understanding Big-O is important, but nothing beats actually measuring performance. Here's how to time algorithms empirically:

import time
import random

def time_sort(sort_func, data):
    """Time a sorting function on a copy of data."""
    test_data = data.copy()
    start = time.perf_counter()
    sort_func(test_data)
    end = time.perf_counter()
    return end - start

# Generate random data
random.seed(42)
sizes = [1000, 2000, 5000, 10000]

for n in sizes:
    data = [random.randint(0, 100_000) for _ in range(n)]

    t_selection = time_sort(selection_sort, data)
    t_insertion = time_sort(insertion_sort, data)
    t_merge     = time_sort(merge_sort, data)
    t_builtin   = time_sort(sorted, data)

    print(f"n={n:>6}: selection={t_selection:.4f}s  "
          f"insertion={t_insertion:.4f}s  "
          f"merge={t_merge:.4f}s  "
          f"builtin={t_builtin:.6f}s")

Output from one run with Python 3.13 (your times will differ, and small timings jump around from run to run):

n=  1000: selection=0.0112s  insertion=0.0111s  merge=0.0010s  builtin=0.000071s
n=  2000: selection=0.0466s  insertion=0.0463s  merge=0.0021s  builtin=0.000147s
n=  5000: selection=0.2758s  insertion=0.3038s  merge=0.0061s  builtin=0.000407s
n= 10000: selection=1.1769s  insertion=1.1555s  merge=0.0123s  builtin=0.000883s

Notice: 1. Selection sort and insertion sort grow roughly 4x when n doubles (O(n²) behavior) — compare n=5000 with n=10000. 2. Merge sort grows a little more than 2x when n doubles (O(n log n) behavior). 3. Python's built-in sort is roughly 10 to 1,000+ times faster than these pure Python implementations. At n=10,000 it's about 14x faster than our merge sort even though both are O(n log n) — that gap is the C implementation and Timsort's tricks. Its roughly 1,300x lead over selection sort breaks down into two multiplied pieces: about 100x from the better algorithm (compare selection sort with merge sort) times that same 14x from C. The C factor stays roughly constant; the algorithm factor keeps widening as n grows.

Elena's Donor Sorting Example

Elena at the nonprofit needs to find her top 10 donors from a list of 50,000 donation records. Here's how she thinks about it:

# Elena's donation records
donations = [
    {"donor": "Garcia Foundation", "amount": 15000},
    {"donor": "Smith Family Trust", "amount": 50000},
    {"donor": "Community Fund", "amount": 8500},
    {"donor": "Anonymous", "amount": 120000},
    {"donor": "Local Business Alliance", "amount": 25000},
    # ... imagine 50,000 records
]

# Find top 10 donors — use sorted() with a key function
top_10 = sorted(donations, key=lambda d: d["amount"], reverse=True)[:10]

for i, d in enumerate(top_10, 1):
    print(f"#{i}: {d['donor']} — ${d['amount']:,}")
# #1: Anonymous — $120,000
# #2: Smith Family Trust — $50,000
# #3: Local Business Alliance — $25,000
# #4: Garcia Foundation — $15,000
# #5: Community Fund — $8,500

Elena could have written her own sorting algorithm, but sorted() with a key and reverse does the job in one readable line. (Sorting all 50,000 records just to keep 10 does some wasted work. The standard library's heapq.nlargest(10, donations, key=lambda d: d["amount"]) finds the top 10 without a full sort. At this size either is effectively instant, so pick whichever reads better to you.) This is what "knowing algorithms" really means — understanding the concepts deeply enough to make good decisions about when to write your own and when to use what's already there.

Choosing the Right Algorithm

When should you use what?

🔄 Check Your Understanding #3

Elena has a list of 100,000 donation records that she needs to search frequently by donor name. She receives about 50 search queries per day. Should she (a) use linear search each time, (b) sort the list once and use binary search for each query, or (c) something else entirely? Justify your answer using Big-O analysis.

19.10 Project Checkpoint: TaskFlow v1.8

🔗 Connection to Chapter 18: In v1.7, you added recursive search for nested categories. Now we add custom sorting and binary search to make TaskFlow's data handling more powerful.

In this checkpoint, you'll add two capabilities to TaskFlow:

1. Custom sorting — sort tasks by priority, due date, creation date, or title using key functions and lambda
2. Binary search — search for a task by title in a sorted task list

Tasks are still v1.5's Task objects, with the same "high", "medium", and "low" priorities you've used since v1.3. Those strings sort alphabetically ("high" < "low" < "medium"), which is the wrong order, so the priority key function translates each one into its rank with PRIORITY_ORDER, the same dictionary v1.3's __lt__ and v1.5's sorted_by_priority() rely on. A key function is exactly the place for that kind of translation. Like v1.6 and v1.7, the checkpoint uses plain functions over a list of tasks so the sorting and searching code stands out.

v1.8 Feature: Custom Sorting and Binary Search

"""TaskFlow v1.8 — Custom sorting and binary search."""

from dataclasses import asdict, dataclass, field
from datetime import datetime

VALID_PRIORITIES = ("high", "medium", "low")
PRIORITY_ORDER = {"high": 0, "medium": 1, "low": 2}  # same ranking as v1.3

# Task is v1.5's dataclass, unchanged (see code/project-checkpoint.py)


# --- Sorting Functions ---

def sort_tasks(tasks: list[Task], sort_by: str = "priority",
               descending: bool = False) -> list[Task]:
    """Sort tasks by a given criterion.

    Args:
        tasks: List of Task objects.
        sort_by: One of "priority", "due_date", "created_at", "title".
        descending: If True, sort in descending order.

    Returns:
        A new sorted list (does not modify the original).
    """
    key_functions = {
        "priority": lambda t: PRIORITY_ORDER[t.priority],
        "due_date": lambda t: t.due_date if t.due_date else "9999-12-31",
        "created_at": lambda t: t.created_at,
        "title": lambda t: t.title.lower(),
    }

    if sort_by not in key_functions:
        raise ValueError(
            f"Invalid sort_by: '{sort_by}'. "
            f"Choose from: {', '.join(key_functions)}"
        )

    return sorted(tasks, key=key_functions[sort_by], reverse=descending)


# --- Binary Search on Sorted Tasks ---

def binary_search_task(sorted_tasks: list[Task], title: str) -> int:
    """Binary search for a task by title in a title-sorted list.

    Args:
        sorted_tasks: List of tasks sorted by title (ascending, case-insensitive).
        title: The title to search for.

    Returns:
        Index of the task, or -1 if not found.
    """
    target = title.lower()
    low = 0
    high = len(sorted_tasks) - 1

    while low <= high:
        mid = (low + high) // 2
        mid_title = sorted_tasks[mid].title.lower()

        if mid_title == target:
            return mid
        elif mid_title < target:
            low = mid + 1
        else:
            high = mid - 1

    return -1


# --- Demo ---

def main():
    # Create sample tasks
    tasks = [
        Task("Buy groceries", priority="medium", due_date="2025-03-15"),
        Task("Call dentist", priority="high", due_date="2025-03-14"),
        Task("Study Python", priority="high", due_date="2025-03-16"),
        Task("Do laundry", priority="low", due_date="2025-03-14"),
        Task("Pay rent", priority="high", due_date="2025-03-01"),
        Task("Write report", priority="medium", due_date="2025-03-20"),
    ]

    # Sort by priority
    print("=== Tasks by Priority ===")
    for task in sort_tasks(tasks, sort_by="priority"):
        print(f"  [{task.priority}] {task.title} (due: {task.due_date})")

    # Sort by due date
    print("\n=== Tasks by Due Date ===")
    for task in sort_tasks(tasks, sort_by="due_date"):
        print(f"  {task.due_date}: {task.title}")

    # Sort by title (for binary search)
    print("\n=== Tasks by Title (for search) ===")
    by_title = sort_tasks(tasks, sort_by="title")
    for i, task in enumerate(by_title):
        print(f"  [{i}] {task.title}")

    # Binary search
    print("\n=== Binary Search ===")
    for term in ["Pay rent", "Walk dog", "Study Python"]:
        idx = binary_search_task(by_title, term)
        if idx != -1:
            print(f"  Found '{term}' at index {idx}")
        else:
            print(f"  '{term}' not found")

    # Multi-key sort: priority first, then due date
    print("\n=== Tasks by Priority, then Due Date ===")
    multi_sorted = sorted(
        tasks,
        key=lambda t: (PRIORITY_ORDER[t.priority],
                       t.due_date if t.due_date else "9999-12-31")
    )
    for task in multi_sorted:
        print(f"  [{task.priority}] {task.due_date}: {task.title}")

    # Descending: "high" ranks first, so reversing puts "low" tasks first
    print("\n=== Tasks by Priority (Descending: Least Urgent First) ===")
    for task in sort_tasks(tasks, sort_by="priority", descending=True):
        print(f"  [{task.priority}] {task.title}")

    # Error handling for an invalid sort key
    print("\n=== Invalid Sort Key (Error Handling) ===")
    try:
        sort_tasks(tasks, sort_by="color")
    except ValueError as e:
        print(f"  Caught error: {e}")


if __name__ == "__main__":
    main()

Expected output:

=== Tasks by Priority ===
  [high] Call dentist (due: 2025-03-14)
  [high] Study Python (due: 2025-03-16)
  [high] Pay rent (due: 2025-03-01)
  [medium] Buy groceries (due: 2025-03-15)
  [medium] Write report (due: 2025-03-20)
  [low] Do laundry (due: 2025-03-14)

=== Tasks by Due Date ===
  2025-03-01: Pay rent
  2025-03-14: Call dentist
  2025-03-14: Do laundry
  2025-03-15: Buy groceries
  2025-03-16: Study Python
  2025-03-20: Write report

=== Tasks by Title (for search) ===
  [0] Buy groceries
  [1] Call dentist
  [2] Do laundry
  [3] Pay rent
  [4] Study Python
  [5] Write report

=== Binary Search ===
  Found 'Pay rent' at index 3
  'Walk dog' not found
  Found 'Study Python' at index 4

=== Tasks by Priority, then Due Date ===
  [high] 2025-03-01: Pay rent
  [high] 2025-03-14: Call dentist
  [high] 2025-03-16: Study Python
  [medium] 2025-03-15: Buy groceries
  [medium] 2025-03-20: Write report
  [low] 2025-03-14: Do laundry

=== Tasks by Priority (Descending: Least Urgent First) ===
  [low] Do laundry
  [medium] Buy groceries
  [medium] Write report
  [high] Call dentist
  [high] Study Python
  [high] Pay rent

=== Invalid Sort Key (Error Handling) ===
  Caught error: Invalid sort_by: 'color'. Choose from: priority, due_date, created_at, title

What You Practiced

• Key functions and lambda: sort_tasks() uses a dictionary of lambda expressions to support multiple sort criteria, including one that ranks priority names instead of comparing them alphabetically
• Multi-key sorting: Sorting by priority first, then by due date within each priority level
• Binary search on structured data: binary_search_task() adapts binary search to work with Task objects, comparing by one attribute (title)
• Separation of concerns: Sorting and searching are separate functions that can be composed

Stretch Goals

1. Add a sort_tasks() option that sorts by number of days until due date (relative to today)
2. Implement a function find_tasks_in_range(sorted_tasks, min_priority, max_priority) that takes a list sorted by priority and uses binary search principles (or bisect) to find all tasks within a priority range, such as "high" through "medium" (compare the priorities' PRIORITY_ORDER ranks, not the strings)
3. Add timing measurements: compare how long it takes to find a task using linear search vs. sorting first and then binary searching

Chapter Summary

You've now implemented five of the most important algorithms in computer science and learned when each is the right tool:

• Linear search (O(n)) — simple, works on any data, but doesn't scale
• Binary search (O(log n)) — blazingly fast, but requires sorted data
• Selection sort (O(n²)) — simple but always slow
• Insertion sort (O(n²)) — great for small or nearly-sorted data
• Merge sort (O(n log n)) — reliable and predictable, uses extra space
• Python's Timsort — the best of both worlds; use it

🔗 Spaced Review: In Chapter 8, you learned in, .sort(), sorted(), .index(), and slicing — all of which you used throughout this chapter. In Chapter 17, you learned Big-O notation, which gave you the vocabulary to compare algorithms. In Chapter 18, you learned recursion, which made merge sort possible. Each chapter builds on the last. That's not a coincidence — that's how knowledge works.

Most importantly, you've developed algorithmic intuition — the ability to look at a problem and reason about which approach will scale and which will break down. This is one of the most valuable skills in computer science, and it extends far beyond sorting and searching. In Chapter 20, you'll apply this same thinking to stacks, queues, and other abstract data structures that power the software you use every day.

🧪 Experiment: Want to feel the difference between O(n²) and O(n log n)? Run selection sort and merge sort on a list of 100,000 random integers. Selection sort will take a minute or more (about 100 times longer than at 10,000 items). Merge sort will finish in well under a second. Python's built-in sorted() will finish before you can blink. That's the power of choosing the right algorithm.