Chapter 19 Key Takeaways

One-Sentence Summary

Searching and sorting are the most fundamental operations in computer science — linear search (O(n)) and binary search (O(log n)) find data, while selection sort (O(n²)), insertion sort (O(n²)), and merge sort (O(n log n)) organize it, and Python's built-in Timsort combines the best of all worlds.

Core Concepts

  1. Linear search is simple but slow. It checks every element in order, taking O(n) time in the worst case. It works on unsorted data and is the right choice for small lists or one-time searches.

  2. Binary search is fast but demanding. It eliminates half the data with each comparison, achieving O(log n). The trade-off: data must be sorted first. For a billion elements, that's ~30 comparisons instead of a billion.

  3. Selection sort always does O(n²) work. It finds the minimum element repeatedly and swaps it into place. Simple to understand, but never adapts to favorable input.

  4. Insertion sort adapts to its input. It builds the sorted list one element at a time. O(n²) worst case, but O(n) on nearly-sorted data — which makes it a critical building block for more advanced algorithms.

  5. Merge sort guarantees O(n log n). It divides the list in half, recursively sorts each half, and merges the results. Consistent performance at the cost of O(n) extra memory.

  6. Python's Timsort is the practical winner. The built-in sorted() and .sort() use Timsort — a hybrid of merge sort and insertion sort, written in optimized C. It's stable, adaptive, and nearly impossible to outperform in Python.

  7. Key functions define "what to sort by." The key parameter in sorted() and .sort() accepts a function (often a lambda) that transforms each element into a comparison value. Multi-key sorting uses tuples.

  8. Stability matters for multi-key sorting. A stable sort preserves the relative order of equal elements. Python's Timsort is stable, which enables reliable multi-pass sorting strategies.

  9. The sorting/searching trade-off is universal. Sorting data is expensive but enables fast binary search. Whether to sort depends on how many searches you'll perform versus how often the data changes.

  10. Empirical timing confirms theory. Big-O tells you how algorithms scale, but time.perf_counter() tells you how they actually perform on your machine with your data. Both perspectives matter.

Algorithm Comparison Table

Algorithm Best Average Worst Space Stable In-place Adaptive
Linear Search O(1) O(n) O(n) O(1) — — —
Binary Search O(1) O(log n) O(log n) O(1) — — —
Selection Sort O(n²) O(n²) O(n²) O(1) No Yes No
Insertion Sort O(n) O(n²) O(n²) O(1) Yes Yes Yes
Merge Sort O(n log n) O(n log n) O(n log n) O(n) Yes No No
Python Timsort O(n) O(n log n) O(n log n) O(n) Yes No Yes

Essential Code Patterns

# Linear search
def linear_search(data, target):
    for i in range(len(data)):
        if data[i] == target:
            return i
    return -1

# Binary search (data MUST be sorted)
def binary_search(data, target):
    low, high = 0, len(data) - 1
    while low <= high:
        mid = (low + high) // 2
        if data[mid] == target:
            return mid
        elif data[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

# Built-in sorting
sorted(data)                                # New sorted list
data.sort()                                 # Sort in place (returns None)
sorted(data, reverse=True)                  # Descending
sorted(data, key=len)                       # By length
sorted(data, key=lambda x: x["gpa"])        # By dictionary field
sorted(data, key=lambda x: (x[0], x[1]))   # Multi-key

Common Mistakes to Avoid

Mistake Fix
result = my_list.sort() (result is None) Use result = sorted(my_list)
Binary search on unsorted data Always sort first or verify sorted order
while low < high in binary search Use while low <= high
low = mid instead of low = mid + 1 Skip past checked element to avoid infinite loop
Writing custom sorts in production Use sorted() or .sort() with a key function

Checklist: Before Moving to Chapter 20

  • [ ] Can implement linear search and binary search from scratch
  • [ ] Can trace binary search step-by-step on a small list
  • [ ] Can implement selection sort, insertion sort, and merge sort
  • [ ] Can explain why merge sort is O(n log n) using the recursion tree
  • [ ] Can use sorted() and .sort() with key, reverse, and lambda
  • [ ] Can sort structured data (lists of dicts/tuples) by multiple criteria
  • [ ] Can explain when to use each algorithm (time, space, stability trade-offs)
  • [ ] Built TaskFlow v1.8 with custom sorting and binary search