Chapter 19: Searching and Sorting: Classic Algorithms

"If you want to be a good programmer, you need to know algorithms. If you want to be a great programmer, you need to know when to use them — and when not to." — Robert Sedgewick

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 processes over 8.5 billion searches per 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 lists under a few hundred elements, the overhead of fancier algorithms isn't worth it.
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. 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. The legendary computer scientist Donald Knuth said that while the first binary search was published in 1946, the first bug-free binary search wasn't published 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 (historical)

In languages like C and Java, (low + high) can overflow if both are large integers. The safe formula is low + (high - low) // 2. In Python, integers have arbitrary precision, so this isn't an issue — but it's good to know if you use other languages.

⚠️ 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.

🔄 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
        No swap needed (already in place)
        Result: [11, 12, 22, 25, 64]
                 ✓   ✓   ✓   ✓   ✓

Analysis

Selection sort always performs the same number of comparisons regardless of the input: n(n-1)/2. Even if the list is already sorted, it still scans through every unsorted element to confirm the minimum.

Selection sort is simple to understand and implement, which makes it a great teaching tool. But O(n²) makes 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). This property makes it useful as a finishing step in 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 section 18.3 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.

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 alternating between the tops of each pile. 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]

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)

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 divides the data into small chunks called "runs."
2. It sorts each run using insertion sort (which is fast for small, nearly-sorted sequences).
3. It merges the runs using a merge sort strategy.

Timsort is O(n log n) in the worst case and O(n) in the best case (already-sorted data). 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.

✅ Best Practice: Unless you're in a CS algorithms course (like right now), use sorted() or .sort(). They're faster, more correct, 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 memory is extremely constrained.
• 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")

Typical output (times vary by machine):

n=  1000: selection=0.0301s  insertion=0.0215s  merge=0.0025s  builtin=0.000065s
n=  2000: selection=0.1180s  insertion=0.0861s  merge=0.0054s  builtin=0.000152s
n=  5000: selection=0.7340s  insertion=0.5310s  merge=0.0152s  builtin=0.000432s
n= 10000: selection=2.9650s  insertion=2.1290s  merge=0.0330s  builtin=0.000980s

Notice: 1. Selection sort and insertion sort grow roughly 4x when n doubles (O(n²) behavior). 2. Merge sort grows roughly 2x when n doubles (O(n log n) behavior). 3. Python's built-in sort is 30-3,000x faster than pure Python implementations — because it's written in C.

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. 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

v1.8 Feature: Custom Sorting and Binary Search

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

from datetime import datetime


def create_task(title: str, priority: int = 3,
                due_date: str = "", category: str = "General") -> dict:
    """Create a task dictionary with metadata."""
    return {
        "title": title,
        "priority": priority,
        "due_date": due_date,
        "category": category,
        "created": datetime.now().isoformat(),
        "done": False,
    }


# --- Sorting Functions ---

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

    Args:
        tasks: List of task dictionaries.
        sort_by: One of "priority", "due_date", "created", "title".
        descending: If True, sort in descending order.

    Returns:
        A new sorted list (does not modify the original).
    """
    key_functions = {
        "priority": lambda t: t["priority"],
        "due_date": lambda t: t["due_date"] if t["due_date"] else "9999-12-31",
        "created": lambda t: t["created"],
        "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[dict], 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 = [
        create_task("Buy groceries", priority=2, due_date="2025-03-15"),
        create_task("Call dentist", priority=1, due_date="2025-03-14"),
        create_task("Study Python", priority=1, due_date="2025-03-16"),
        create_task("Do laundry", priority=3, due_date="2025-03-14"),
        create_task("Pay rent", priority=1, due_date="2025-03-01"),
        create_task("Write report", priority=2, due_date="2025-03-20"),
    ]

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

    # Sort by due date
    print("\n=== Tasks by Due Date ===")
    by_date = sort_tasks(tasks, sort_by="due_date")
    for task in by_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 ===")
    search_terms = ["Pay rent", "Walk dog", "Study Python"]
    for term in search_terms:
        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: (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']}")


if __name__ == "__main__":
    main()

Expected output:

=== Tasks by Priority ===
  [1] Call dentist (due: 2025-03-14)
  [1] Study Python (due: 2025-03-16)
  [1] Pay rent (due: 2025-03-01)
  [2] Buy groceries (due: 2025-03-15)
  [2] Write report (due: 2025-03-20)
  [3] 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 ===
  [1] 2025-03-01: Pay rent
  [1] 2025-03-14: Call dentist
  [1] 2025-03-16: Study Python
  [2] 2025-03-15: Buy groceries
  [2] 2025-03-20: Write report
  [3] 2025-03-14: Do laundry

What You Practiced

• Key functions and lambda: sort_tasks() uses a dictionary of lambda expressions to support multiple sort criteria
• 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 dictionaries, comparing by a specific field
• 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 uses binary search principles to find all tasks within a priority range
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 minutes. Merge sort will finish in under a second. Python's built-in sorted() will finish before you can blink. That's the power of choosing the right algorithm.