Further Reading: Searching and Sorting

Algorithm Fundamentals

Grokking Algorithms, 2nd Edition, by Aditya Bhargava (Manning, 2024). (Tier 1) The best visual introduction to algorithms for beginners. Chapters 1–4 cover binary search, selection sort, recursion, and quicksort (with a comparison to merge sort) using excellent hand-drawn illustrations. If the textbook explanation of any algorithm didn't fully click, this book will get you there.
Problem Solving with Algorithms and Data Structures using Python, by Brad Miller and David Ranum (free online at runestone.academy). (Tier 1) An interactive, open-source textbook with embedded Python exercises. Chapters on searching and sorting include visualizations where you can step through each algorithm. Excellent for building intuition through experimentation.

Introduction to Algorithms (CLRS), 4th Edition, by Cormen, Leiserson, Rivest, and Stein (MIT Press, 2022). (Tier 2) The definitive algorithms textbook used in university CS programs worldwide. Chapter 2 (insertion sort and merge sort), Chapter 4 (divide-and-conquer and solving recurrences), Chapter 7 (quicksort), and Chapter 8 (linear-time sorting and the comparison-sort lower bound) provide rigorous mathematical analysis. Not a beginner book, but the gold standard reference.
The Art of Computer Programming, Volume 3: Sorting and Searching, by Donald Knuth (Addison-Wesley, 1998). (Tier 3) Knuth's magnum opus dedicates an entire volume of nearly 800 pages to sorting and searching. Exhaustively thorough and mathematically rigorous. More of a monument than a textbook, but if you want to understand every possible sorting algorithm ever invented, this is where you go.

Python's Sorting HOW TO (docs.python.org/3/howto/sorting.html). (Tier 1) The official Python guide to using sorted(), .sort(), key functions, and operator.itemgetter/operator.attrgetter as alternatives to lambda expressions. Short, practical, and authoritative.
The bisect module documentation (docs.python.org/3/library/bisect.html). (Tier 1) Python's standard library provides bisect.bisect_left(), bisect.bisect_right(), and bisect.insort() for binary search and sorted insertion. Production code should use these instead of hand-written binary search.
Tim Peters' Timsort notes, listsort.txt (github.com/python/cpython/blob/main/Objects/listsort.txt). (Tier 2) Tim Peters' technical description of how Python's list sort works, first written when he implemented Timsort in 2002 (it shipped with Python 2.3) and kept up to date in the CPython source — including the Powersort merge policy adopted in Python 3.11. Readable and fascinating if you want to understand why Python's sort is so fast.

Brin, S. and Page, L. (1998). "The Anatomy of a Large-Scale Hypertextual Web Search Engine." Computer Networks and ISDN Systems 30 (Proceedings of the Seventh International World Wide Web Conference). (Tier 2) Google's founders describe their Stanford prototype search engine, including PageRank. Surprisingly readable and shows how sorting and ranking transformed web search. Available free online.
Dean, J. and Ghemawat, S. (2004). "MapReduce: Simplified Data Processing on Large Clusters." OSDI '04. (Tier 2) The paper that introduced MapReduce, a framework for processing internet-scale data across thousands of machines. Sorting intermediate results by key — using an external sort when the data doesn't fit in memory — is at its heart. One of the most influential systems papers of the 2000s.

VisuAlgo (visualgo.net/en/sorting). (Tier 1) Interactive visualizations of every sorting algorithm covered in this chapter (and many more). You can step through each algorithm, adjust speed, and use your own input data. The single best tool for building sorting intuition.
Sorting Algorithms Visualized (youtube.com — search "15 Sorting Algorithms in 6 Minutes"). (Tier 1) Several popular YouTube videos show sorting algorithms running side-by-side with audio representations (each comparison plays a tone). Surprisingly mesmerizing, and excellent for understanding how different algorithms approach the same problem differently.
Big-O Cheat Sheet (bigocheatsheet.com). (Tier 1) A one-page reference card for the time and space complexity of common algorithms and data structures. Useful as a quick reference while working through exercises.

Quicksort (not covered in this chapter). (Tier 2) Quicksort is another O(n log n) divide-and-conquer algorithm that is often faster than merge sort in practice because it sorts in-place. It's covered in Exercise E.4 and in most intermediate algorithms courses. Python's sorted() doesn't use quicksort (it uses Timsort), but quicksort is still one of the most important algorithms to learn eventually.
Radix sort and counting sort — non-comparison sorts. (Tier 3) All algorithms in this chapter are comparison-based — they learn about data by comparing pairs of elements. A mathematical result called the "comparison-based lower bound" proves that no comparison sort can beat roughly n log n comparisons in the worst case. (Timsort's O(n) best case doesn't break this rule — it only happens on lucky inputs such as already-sorted data.) But non-comparison sorts like radix sort and counting sort can achieve O(n) time by exploiting the structure of the data (e.g., sorting integers by individual digits). These are fascinating but specialized.